Simple Concurrent Connected Components Algorithms

Sixue Cliff Liu, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review


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 O(lg n) step and O(m lg n) work bounds.1 For two others, we obtain O(lg2 n) step and O(m lg2 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.

Original languageEnglish (US)
Article number9
JournalACM Transactions on Parallel Computing
Issue number2
StatePublished - Sep 1 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Modeling and Simulation
  • Hardware and Architecture
  • Computer Science Applications
  • Computational Theory and Mathematics


  • Connected components
  • PRAM algorithms
  • simplicity


Dive into the research topics of 'Simple Concurrent Connected Components Algorithms'. Together they form a unique fingerprint.

Cite this