ABSTRACT

Improving a long chain of works we obtain a randomized EREW PRAM algorithm for finding the connected compo- nents of a graph G = (V,E) with n vertices and m edges in O(log n) time using an optimal number of O((m+n)/log n) processors. The result returned by the algorithm is always correct. The probability that the algorithm will not com- plete in O(log n) time is at most n for any desired c > 0. The best deterministic EREW PRAM connectivity algo- rithm, obtained by Chong and Lam, runs in O(log n log log n) time using m + n processors.