License
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2019.3
URN: urn:nbn:de:0030-drops-100292
URL: http://drops.dagstuhl.de/opus/volltexte/2018/10029/
Go to the corresponding OASIcs Volume Portal


Liu, Sixue ; Tarjan, Robert E.

Simple Concurrent Labeling Algorithms for Connected Components

pdf-format:
OASIcs-SOSA-2019-3.pdf (0.7 MB)


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.

BibTeX - Entry

@InProceedings{liu_et_al:OASIcs:2018:10029,
  author =	{Sixue Liu and Robert E. Tarjan},
  title =	{{Simple Concurrent Labeling Algorithms for Connected Components}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{3:1--3:20},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{69},
  editor =	{Jeremy T. Fineman and Michael Mitzenmacher},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10029},
  URN =		{urn:nbn:de:0030-drops-100292},
  doi =		{10.4230/OASIcs.SOSA.2019.3},
  annote =	{Keywords: Connected Components, Concurrent Algorithms}
}

Keywords: Connected Components, Concurrent Algorithms
Seminar: 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Issue Date: 2018
Date of publication: 18.12.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI