Accession Number : ADA114875

Title :   The Expected Time Complexity of Parallel Graph and Digraph Algorithms.

Descriptive Note : Technical rept.,


Personal Author(s) : Reif,John H ; Spirakis,Paul

PDF Url : ADA114875

Report Date : Apr 1982

Pagination or Media Count : 31

Abstract : 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 O(loglog n) for a parallel RAM model (RP-RAM) which allows random resolution of write conflicts, and expected time O(log 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 O(loglog n)(2) for the RP-RAM and O(log n. (loglog n) (2)) for the P-RAM. Also we show that the problem of random graph isomorphism has expected parallel time O(loglog n) and O(log 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 O(log-loglog n) with n (O)(1) time on a Turing Machine given random graphs as inputs.

Descriptors :   *Graphs, Algorithms, Problem solving, Parallel processing, Sequences, Trees

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE