A contraction-recursive algorithm for treewidth

DOI10.4230/LIPICS.IPEC.2023.34MaRDI QIDQ6926173zbMATH OpenFDO

Authors Hisao Tamaki

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

contractiontreewidthgraph algorithmexact computationcertifying algorithmsBT dynamic programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A practical algorithm for making filled graphs minimal
• Complexity of Finding Embeddings in a k-Tree
• Graph minors. II. Algorithmic aspects of tree-width
• Minimal triangulations of graphs: a survey
• On Exact Algorithms for Treewidth
• On Tamaki's Algorithm to Compute Treewidths.
• Parameterized algorithms
• Positive-instance driven dynamic programming for treewidth
• Safe separators for treewidth
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth computation and extremal combinatorics
• Treewidth computations. I: Upper bounds
• Treewidth computations. II. Lower bounds

This page was built for publication: A contraction-recursive algorithm for treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6926173)