Connected Components on a PRAM in Log Diameter Time
Sixue Cliff Liu, Robert Endre Tarjan, Peilin Zhong · 2020
We present an O(log d + log logm/n n)-time randomized PRAM algorithm for computing the connected components of an n-vertex, m-edge undirected graph with maximum component diameter d. The algorithm runs on an ARBITRARY CRCW (concurrent-read, concurrent-write with arbitrary write resolution) PRAM using O(m) processors. The time bound holds with good probability.