1 Search Results for "Schnurbusch, Daniela"

Document
DOI: 10.4230/LIPIcs.SEA.2021.9
On Tamaki’s Algorithm to Compute Treewidths

Authors: Ernst Althaus, Daniela Schnurbusch, Julian Wüschner, and Sarah Ziegler

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
We revisit the exact algorithm to compute the treewidth of a graph of Tamaki and present it in a way that facilitates improvements. The so-called I-blocks and O-blocks enumerated by the algorithm are interpreted as subtrees of a tree-decomposition that is constructed. This simplifies the proof of correctness and allows to discard subtrees from the enumeration by some simple observations. In our experiments, we show that one of these modifications in particular reduces the number of enumerated objects considerably.
Cite as

Ernst Althaus, Daniela Schnurbusch, Julian Wüschner, and Sarah Ziegler. On Tamaki’s Algorithm to Compute Treewidths. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{althaus_et_al:LIPIcs.SEA.2021.9,
  author =	{Althaus, Ernst and Schnurbusch, Daniela and W\"{u}schner, Julian and Ziegler, Sarah},
  title =	{{On Tamaki’s Algorithm to Compute Treewidths}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.9},
  URN =		{urn:nbn:de:0030-drops-137818},
  doi =		{10.4230/LIPIcs.SEA.2021.9},
  annote =	{Keywords: Tree Decomposition, Exact Algorithm, Algorithms Engineering}
}
  • Refine by Author
  • 1 Althaus, Ernst
  • 1 Schnurbusch, Daniela
  • 1 Wüschner, Julian
  • 1 Ziegler, Sarah

  • Refine by Classification
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 1 Algorithms Engineering
  • 1 Exact Algorithm
  • 1 Tree Decomposition

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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