Expected parallel time and sequential space complexity of graph and digraph problems

This paper determines upper bounds on the expected time complexity for a variety of parallel algorithms for undirected and directed random graph problems. For connectivity, biconnectivity, transitive closure, minimum spanning trees, and all pairs minimum cost paths, we prove the expected time to be O(log log n) for the CRCW PRAM (this parallel RAM machine allows resolution of write conflicts) and O(log n · log log n) for the CREW PRAM (which allows simultaneous reads but not simultaneous writes). We also show that the problem of graph isomorphism has expected parallel time O(log log n) for the CRCW PRAM and O(log n) for the CREW PRAM. Most of these results follow because of upper bounds on the mean depth of a graph, derived in this paper, for more general graphs than was known before. For undirected connectivity especially, we present a new probabilistic algorithm which runs on a randomized input and has an expected running time of O(log log n) on the CRCW PRAM, with O(n) expected number of processors only. Our results also improve known upper bounds on the expected space required for sequential graph algorithms. For example, we show that the problems of finding connected components, transitive closure, minimum spanning trees, and minimum cost paths have expected sequential space O(log n · log log n) on a deterministic Turing Machine. We use a simulation of the CRCW PRAM to get these expected sequential space bounds.

Duke Scholars

Author John H. Reif Computer Science