Finding connected components in O(log n loglog n) time on the EREW PRAM
Ka Wong Chong, Tak‐Wah Lam · The HKU Scholars Hub (University of Hong Kong) · 1993
In this paper we present a new parallel algorithm for finding the connected components of an undirected graph. On a graph with n vertices and m edges, the algorithm runs in O(log n loglog n) time using n+m processors on an EREW (exclusive-read and exclusive-write) PRAM. Prior to our work, the best known exclusive-write algorithm for this problem requires O(log1.5 n) time using n+m processors [JM91, KNP92].