Connected Components in Linear Work and Near-Optimal Time

Alireza Farhadi, S. Cliff Liu, Elaine Shi

Computing the connected components of a graph is a fundamental problem in algorithmic graph theory. A major question in this area is whether we can compute connected components in…