Simple Concurrent Connected Components Algorithms

Sixue Cliff Liu, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

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 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
Volume9
Issue number2
DOIs
StatePublished - Sep 1 2022

All Science Journal Classification (ASJC) codes

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

Keywords

  • Connected components
  • PRAM algorithms
  • simplicity

Fingerprint

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

Cite this