Expected parallel time and sequential space complexity of graph and digraph problems (Q1186789)

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\cdot\log\log n)\) for the CREW PRAM (which allows simultaneous reads but not simultaneous writes). We also show that the problem of graphs 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, 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 problem of finding connected components, transitive closure, minimum spanning trees, and minimum cost paths have expected sequential space \(O(\log n\cdot\log\log n)\) on a deterministic Turing Machine. We use a simulation of the CRCW PRAM to get these expected sequential space bounds.