Fast connected components algorithms for the EREW PRAM

We present fast and efficient parallel algorithms for finding the connected components of an undirected graph. These algorithms run on the exclusive-r ead, exclusive-write (EREW) PRAM. On a graph with n vertices and m edges, o ur randomized algorithm runs in O(log n) time using (m + n(1+epsilon)) = lo g n EREW processors (for any fixed epsilon > 0). A variant uses (m + n)= lo g n processors and runs in O(log n log log n) time. A deterministic version of the algorithm runs in O(log(1.5) n) time using m + n EREW processors.