2 Search Results for "Liu, Sixue"

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-dev.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-dev.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}
}
  • Refine by Author
  • 2 Liu, Sixue
  • 1 Tarjan, Robert E.

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms

  • Refine by Keyword
  • 1 Concurrent Algorithms
  • 1 Connected Components
  • 1 Satisfiability
  • 1 derandomization
  • 1 local search

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact