Skip to main content

Simple Concurrent Labeling Algorithms for Connected Components

Author(s): Liu, Sixue; Tarjan, Robert E

To refer to this page use:
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(lg^2 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.
Publication Date: 2018
Citation: Liu, Sixue, and Robert E. Tarjan. "Simple Concurrent Labeling Algorithms for Connected Components." In 2nd Symposium on Simplicity in Algorithms 69 (2018): pp. 3:1-3:20. doi:10.4230/OASIcs.SOSA.2019.3
DOI: 10.4230/OASIcs.SOSA.2019.3
ISSN: 2190-6807
Pages: 3:1 - 3:20
Type of Material: Conference Article
Journal/Proceeding Title: 2nd Symposium on Simplicity in Algorithms
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.