1 Search Results for "Ziobro, Michal"

Document
DOI: 10.4230/LIPIcs.SEA.2018.29
Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation

Authors: Michal Ziobro and Marcin Pilipczuk

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
The notion of treewidth, introduced by Robertson and Seymour in their seminal Graph Minors series, turned out to have tremendous impact on graph algorithmics. Many hard computational problems on graphs turn out to be efficiently solvable in graphs of bounded treewidth: graphs that can be sweeped with separators of bounded size. These efficient algorithms usually follow the dynamic programming paradigm. In the recent years, we have seen a rapid and quite unexpected development of involved techniques for solving various computational problems in graphs of bounded treewidth. One of the most surprising directions is the development of algorithms for connectivity problems that have only single-exponential dependency (i.e., 2^{{O}(t)}) on the treewidth in the running time bound, as opposed to slightly superexponential (i.e., 2^{{O}(t log t)}) stemming from more naive approaches. In this work, we perform a thorough experimental evaluation of these approaches in the context of one of the most classic connectivity problem, namely Hamiltonian Cycle.
Cite as

Michal Ziobro and Marcin Pilipczuk. Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ziobro_et_al:LIPIcs.SEA.2018.29,
  author =	{Ziobro, Michal and Pilipczuk, Marcin},
  title =	{{Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{29:1--29:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.29},
  URN =		{urn:nbn:de:0030-drops-89648},
  doi =		{10.4230/LIPIcs.SEA.2018.29},
  annote =	{Keywords: Empirical Evaluation of Algorithms, Treewidth, Hamiltonian Cycle}
}
  • Refine by Author
  • 1 Pilipczuk, Marcin
  • 1 Ziobro, Michal

  • Refine by Classification
  • 1 Theory of computation → Dynamic programming
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Empirical Evaluation of Algorithms
  • 1 Hamiltonian Cycle
  • 1 Treewidth

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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