There is a straightforward algorithm for computing the transitive closure of an n-node directed graph in O (log2 n) time on an EREW-PRAM, using n3/log n processors, or indeed with M (n)/logn processors if one can do serial matrix multiplication in time M (n). Th is 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 AfC algorithm for transitive closure that took about e processors for the single-source problem on a graph with n nodes and e 2 n arcs, or about en processors for the all-pairs problem on the same graph. While we cannot offer an algorithm that good, we can offer algorithms_with the following performance.(1) For single-source, O (nc) time with O (enlm2’) processors, 1 provided e> n2-3c, and (2) for all-pairs,@ no time and d (enlvc) processors, provided e 2 n2-2c. Each of these claims assumes 0< E 5 l/2. Importantly, the algorithms are (only) high-probability algorithms; that is, if they find a path, then a path exists, but they may fail to find a path that exists with probability at most 2-ac, where Q is some positive constant, and c is a multiplier for the time taken by the algorithm. However, we show that incorrect results can be detected, thus putting the algorithm in the “Las Vegas” class. Finally, t Work partially supported by ONR contract N00014-88-K-0166 and a Guggenheim fellowship.

1 6 is the notation, proposed by Luks and furthered by A. Bhnn for “within some number of log factors of.” That is, we say f (n) is s (g (n)) if for some constants c and k, and all sufficiently large n, we have j (n) 5 clogk ng (n). we show how to do “breadth-first-search” with the same performance as we are able to achieve for single-source transitive closure.