Connected Components in O(log3/2 n) Parallel Time for the CREW PRAM

Finding the connected components of an undirected graph G=(V, E) on n=|V| vertices and m=|E| edges is a fundamental computational problem. The best known parallel algorithm for the CREW PRAM model runs in O(log2 n) time using n2/log2 n processors. For the CRCW PRAM model, in which concurrent writing is permitted, the best known algorithm runs in O(log n) time using slightly more than (n+m)/log n processors. Simulating this algorithm on the weaker CREW model increases its running time to O(log2 n). We present here a simple algorithm that runs in O(log3/2 n) time using n+m CREW processors. Finding an o(log2 n) parallel connectivity algorithm for this model was an open problem for many years