Simple Concurrent Labeling Algorithms for Connected Components

2018/12/14 by S. Cliff Liu, Robert E. Tarjan, Liu, S. Cliff +1
Computer Science · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1812.06177

24 pages

arxiv created 2020/03/03 · arxiv updated 2020/03/04

Abstract

We study a class of simple algorithms for concurrently computing the connected components of an n-vertex, m-edge graph. Our algorithms are easy to implement in either the COMBINING CRCW PRAM or the MPC computing model. For two related algorithms in this class, we obtain Θ(\lg n) step and Θ(m \lg n) work bounds. For two others, we obtain O(\lg² n) step and O(m \lg² n) work bounds, which are tight for one of them. All our algorithms are simpler than related algorithms in the literature. We also point out some gaps and errors in the analysis of previous algorithms. Our results show that even a basic problem like connected components still has secrets to reveal.

Related

• Connected Components on a PRAM in Log Diameter Time
• Connected Components in Linear Work and Near-Optimal Time
• Improved Linear-Time Algorithm for Computing the 4-Edge-Connected Components of a Graph
• Optimal component labeling algorithms for mesh-connected computers and VLSI
• On finding 2-cuts and 3-edge-connected components in parallel