A straightforward algorithm exists for computing the transitive closure of an n-node graph in O(log2n) time on an EREW-PRAM using n3/ log n processors. The algorithm is far from optimal when the graph is sparse or when one wants to solve the single source transitive-closure problem.
Assume that the graph has n nodes and e edges, and that 0 < a ≤ .5. The authors provide high-probability algorithms for two cases. For single-source, their algorithm uses O(na) time with O(en1−2a) processors, provided e ≥ n2−3a; for the all-pairs problem, their algorithm requires O(na) time with O(en1−a) processors, provided e ≥ n2−2a.
A high-probability algorithm has the following characteristic: if it reports a path, then the path does exist, but it may fail to find a path with a fixed probability. The authors show that incorrect results can be detected. Therefore, their algorithms are in the “Las Vegas” class. Their algorithms depend on a result of Greene and Knuth that if one picks s “distinguished” nodes at random, then the probability that a path has a gap longer than O((n log n)/s) with no distinguished node is fixed.
The paper closes with several open questions. Do deterministic algorithms with the same performance exist? Does any of the material generalize to the shortest-path problem, where arcs initially have arbitrary weights?
