Simple Concurrent Connected Components Algorithms

Sixue Cliff Liu; Robert Endre Tarjan

doi:10.1145/3543546

Simple Concurrent Connected Components Algorithms

Sixue Cliff Liu, Robert Endre Tarjan

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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 language	English (US)
Article number	9
Journal	ACM Transactions on Parallel Computing
Volume	9
Issue number	2
DOIs	https://doi.org/10.1145/3543546
State	Published - 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

Access to Document

10.1145/3543546

Cite this

@article{f1ccaaab59b84b2c9cb86b80dd9ac6de,

title = "Simple Concurrent Connected Components Algorithms",

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.",

keywords = "Connected components, PRAM algorithms, simplicity",

author = "Liu, {Sixue Cliff} and Tarjan, {Robert Endre}",

note = "Publisher Copyright: {\textcopyright} 2022 Association for Computing Machinery.",

year = "2022",

month = sep,

day = "1",

doi = "10.1145/3543546",

language = "English (US)",

volume = "9",

journal = "ACM Transactions on Parallel Computing",

issn = "2329-4949",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

T1 - Simple Concurrent Connected Components Algorithms

AU - Liu, Sixue Cliff

AU - Tarjan, Robert Endre

PY - 2022/9/1

Y1 - 2022/9/1

N2 - 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.

AB - 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.

KW - Connected components

KW - PRAM algorithms

KW - simplicity

UR - http://www.scopus.com/inward/record.url?scp=85139250656&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85139250656&partnerID=8YFLogxK

U2 - 10.1145/3543546

DO - 10.1145/3543546

M3 - Article

AN - SCOPUS:85139250656

SN - 2329-4949

VL - 9

JO - ACM Transactions on Parallel Computing

JF - ACM Transactions on Parallel Computing

IS - 2

M1 - 9

ER -

Simple Concurrent Connected Components Algorithms

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this