Connected Components on a PRAM in Log Diameter Time

S. Cliff Liu, Robert E. Tarjan, Peilin Zhong

We present an $O(\log d+\log {\log }_{m/n}n)$-time randomized PRAM algorithm for computing the connected components of an $n$-vertex, $m$-edge undirected graph with maximum componen…