Skip to main content

High-Probability Parallel Transitive Closure Algorithms

01 January 1989

New Image

There is a straightforward algorithm for computing the transitive closure of an n-node graph in 0(log sup 2 n) time on an EREW-PRAM, using n sup 3 /log n processors, or indeed with M9n) log n processors if one can do serial matrix multiplication with M(n) processors. This algorithm is within a log factor of optimal in work (processor-time product), for solving the all-pairs transitive-closure problem for dense graphs. However, this algorithm is far from optimal when either (a) the graph is sparse, or (b) we want to solve the single-source transitive closure problem. Ideally, we would like an NC algorithm for transitive closure that took about e processors for the single-source problem on a graph with n nodes and e >= n arcs, or about en processors for the all-pairs problem on the same graph.