TY - GEN
T1 - Simple concurrent labeling algorithms for connected components
AU - Liu, Sixue
AU - Tarjan, Robert E.
N1 - Publisher Copyright:
© Sixue Liu and Robert E. Tarjan.
PY - 2019/1
Y1 - 2019/1
N2 - 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.
AB - 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.
KW - Concurrent Algorithms
KW - Connected Components
UR - http://www.scopus.com/inward/record.url?scp=85073877354&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85073877354&partnerID=8YFLogxK
U2 - 10.4230/OASIcs.SOSA.2019.3
DO - 10.4230/OASIcs.SOSA.2019.3
M3 - Conference contribution
AN - SCOPUS:85073877354
T3 - OpenAccess Series in Informatics
BT - 2nd Symposium on Simplicity in Algorithms, SOSA 2019 - Co-located with the 30th ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
A2 - Fineman, Jeremy T.
A2 - Mitzenmacher, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 2nd Symposium on Simplicity in Algorithms, SOSA 2019
Y2 - 8 January 2019 through 9 January 2019
ER -