Positive-Instance Driven Dynamic Programming for Treewidth.

DOI10.4230/LIPIcs.ESA.2017.68zbMath1442.90198OpenAlexW2897005204MaRDI QIDQ5111757

Hisao Tamaki

Publication date: 27 May 2020

Full work available at URL: https://dblp.uni-trier.de/db/conf/esa/esa2017.html#Tamaki17

zbMATH Keywords

dynamic programmingtreewidthminimal separatorspotential maximal cliquespositive instances

Mathematics Subject Classification ID

Trees (05C05) Decision theory (91B06) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Unnamed Item ⋮ Unnamed Item ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Practical Access to Dynamic Programming on Tree Decompositions ⋮ The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• A note on exact algorithms for vertex ordering problems on graphs
• Graph minors. XX: Wagner's conjecture
• Safe separators for treewidth
• Treewidth computation and extremal combinatorics
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• On exact algorithms for treewidth
• An Iterative Heuristic Algorithm for Tree Decomposition
• Exact Algorithms for Treewidth and Minimum Fill-In
• Encoding Treewidth into SAT
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Pseudo Affine Projection Algorithms Revisited: Robustness and Stability Analysis
• Contraction and Treewidth Lower Bounds
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Positive-Instance Driven Dynamic Programming for Treewidth.