An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (extended abstract)
Shay Halperin, Uri Zwick · 1994
Improving a long chain of works we obtain a randomized EREW PRAM algorithm for finding the connected components 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 complete in O(log n) time is at most n-c for any desired c > 0.