2026-07-20T09:01:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10029 2024-03-06T10:30:32Z ddc:004 open_access

Simple Concurrent Labeling Algorithms for Connected Components Liu, Sixue Tarjan, Robert E. Connected Components Concurrent Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sixue Liu and Robert E. Tarjan 2019 Is Part Of OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SOSA.2019.3 urn:nbn:de:0030-drops-100292 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.3 eng https://creativecommons.org/licenses/by/3.0/legalcode