Simple Parallel Randomized Connected Components Algorithms

Abstract

We study three simple algorithms for concurrently computing connected components in a randomized setting, A, S and P. These algorithms were previously studied in a deterministic setting by Liu and Tarjan, who provided an $O(\log^2 n)$ step bound for A and S, with P remaining unanalyzed.\footnote{We use $\log$ to denote the base two logarithm} In a randomized setting, we provide $O(\log n)$ and $O(\log n \log \log n)$ step bounds for A and S respectively, and a $O(\frac{\log^2 n}{\log \log n})$ bound for P. All results hold with high probability.