DROPS

Document

DOI: 10.4230/OASIcs.SOSA.2019.3

Simple Concurrent Labeling Algorithms for Connected Components

Authors: Sixue Liu and Robert E. Tarjan

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

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.

Cite as

Sixue Liu and Robert E. Tarjan. Simple Concurrent Labeling Algorithms for Connected Components. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

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

Document

DOI: 10.4230/LIPIcs.ICALP.2018.88

Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT

Authors: Sixue Liu

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

We present the current fastest deterministic algorithm for k-SAT, improving the upper bound (2-2/k)^{n + o(n)} due to Moser and Scheder in STOC 2011. The algorithm combines a branching algorithm with the derandomized local search, whose analysis relies on a special sequence of clauses called chain, and a generalization of covering code based on linear programming. We also provide a more intelligent branching algorithm for 3-SAT to establish the upper bound 1.32793^n, improved from 1.3303^n.

Cite as

Sixue Liu. Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 88:1-88:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.ICALP.2018.88,
  author =	{Liu, Sixue},
  title =	{{Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{88:1--88:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.88},
  URN =		{urn:nbn:de:0030-drops-90925},
  doi =		{10.4230/LIPIcs.ICALP.2018.88},
  annote =	{Keywords: Satisfiability, derandomization, local search}
}

Search Results

Documents authored by Liu, Sixue

Simple Concurrent Labeling Algorithms for Connected Components

Abstract

Cite as

Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT

Abstract

Cite as

Thanks for your feedback!

Could not send message