An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph
Hillel Gazit · SIAM Journal on Computing · 1991
A parallel randomized algorithm for finding the connected components of an undirected graph is presented. The algorithm has an expected running time of $T = O(\log (n))$ with $P = O((m + n) / \log (n))$ processors, where m is the number of edges and n is the number of vertices. The algorithm is optimal in the sense that the product $P \cdot T$ is a linear function of the input size. The algorithm requires $O(m + n)$ space, which is the input size, so it is optimal in space as well.