License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2021.9
URN: urn:nbn:de:0030-drops-137818
Go to the corresponding LIPIcs Volume Portal

Althaus, Ernst ; Schnurbusch, Daniela ; Wüschner, Julian ; Ziegler, Sarah

On Tamaki’s Algorithm to Compute Treewidths

LIPIcs-SEA-2021-9.pdf (0.8 MB)


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.

BibTeX - Entry

  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 =		{},
  URN =		{urn:nbn:de:0030-drops-137818},
  doi =		{10.4230/LIPIcs.SEA.2021.9},
  annote =	{Keywords: Tree Decomposition, Exact Algorithm, Algorithms Engineering}

Keywords: Tree Decomposition, Exact Algorithm, Algorithms Engineering
Collection: 19th International Symposium on Experimental Algorithms (SEA 2021)
Issue Date: 2021
Date of publication: 31.05.2021
Supplementary Material: Software: archived at:

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