
Accession Number : ADA114875
Title : The Expected Time Complexity of Parallel Graph and Digraph Algorithms.
Descriptive Note : Technical rept.,
Corporate Author : HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB
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 (RPRAM) which allows random resolution of write conflicts, and expected time O(log n loglog n) for the PRAM 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 RPRAM and O(log n. (loglog n) (2)) for the PRAM. 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(logloglog 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