Simple concurrent labeling algorithms for connected components

Sixue Liu, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present new concurrent labeling algorithms for finding connected components, and we study their theoretical efficiency. Even though many such algorithms have been proposed and many experiments with them have been done, our algorithms are simpler. We obtain an O(lg n) step bound for two of our algorithms using a novel multi-round analysis. We conjecture that our other algorithms also take O(lg n) steps but are only able to prove an O(lg2 n) bound. We also point out some gaps in previous analyses of similar algorithms. Our results show that even a basic problem like connected components still has secrets to reveal.

Original languageEnglish (US)
Title of host publication2nd Symposium on Simplicity in Algorithms, SOSA 2019 - Co-located with the 30th ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
EditorsJeremy T. Fineman, Michael Mitzenmacher
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770996
DOIs
StatePublished - Jan 2019
Event2nd Symposium on Simplicity in Algorithms, SOSA 2019 - San Diego, United States
Duration: Jan 8 2019Jan 9 2019

Publication series

NameOpenAccess Series in Informatics
Volume69
ISSN (Print)2190-6807

Conference

Conference2nd Symposium on Simplicity in Algorithms, SOSA 2019
CountryUnited States
CitySan Diego
Period1/8/191/9/19

All Science Journal Classification (ASJC) codes

  • Geography, Planning and Development
  • Modeling and Simulation

Keywords

  • Concurrent Algorithms
  • Connected Components

Fingerprint Dive into the research topics of 'Simple concurrent labeling algorithms for connected components'. Together they form a unique fingerprint.

  • Cite this

    Liu, S., & Tarjan, R. E. (2019). Simple concurrent labeling algorithms for connected components. In J. T. Fineman, & M. Mitzenmacher (Eds.), 2nd Symposium on Simplicity in Algorithms, SOSA 2019 - Co-located with the 30th ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 [3] (OpenAccess Series in Informatics; Vol. 69). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/OASIcs.SOSA.2019.3