The Expected Time Complexity of Parallel Graph and Digraph Algorithms.

This paper determines upper bounds on the expected time complexity for a variety of known parallel algorithms for graph problems. For connectivity of both undirected and directed graphs, transitive closure and all pairs minimum cost paths, we prove the expected time is Ologlog n for a parallel RAM model RP-RAM which allows random resolution of write conflicts, and expected time Olog n loglog n for the P-RAM of Wyllie, 79, which allows no write conflicts. We show that the expected parallel time for biconnected components and minimum spanning trees is Ologlog n2 for the RP-RAM and Olog n. loglog n 2 for the P-RAM. Also we show that the problem of random graph isomorphism has expected parallel time Ologlog n and Olog n for the above parallel models, respectively. Our results also improve known upper bounds on the expected space required tor sequential graph algorithms. For example, we show that the problems of finding strong components, transitive closure and minimum cost paths have expected sequential space Olog-loglog n with n O1 time on a Turing Machine given random graphs as inputs.