Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.

DOI10.4230/LIPIcs.MFCS.2019.42OpenAlexW2970851838MaRDI QIDQ5092404

O-joung Kwon, Eduard Eiben, Thekla Hamm, Robert Ganian

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.42

zbMATH Keywords

treewidthfixed-parameter algorithmsparameterized complexityrank-width

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Solving projected model counting by utilizing treewidth and its limits ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kernelization using structural parameters on sparse graph classes
• Fundamentals of parameterized complexity
• Graph minors. III. Planar tree-width
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Generalized coloring for tree-like graphs
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Backdoor treewidth for SAT
• Solving problems on graphs of high rank-width
• Parameterized complexity of vertex colouring
• Reduction algorithms for graphs of small treewidth
• Edge dominating set and colorings on graphs with fixed clique-width
• A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Approximating clique-width and branch-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Between Treewidth and Clique-Width
• Intractability of Clique-Width Parameterizations
• (Meta) Kernelization
• Graph Layout Problems Parameterized by Vertex Cover
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Combining Treewidth and Backdoors for CSP.
• Immersions in Highly Edge Connected Graphs
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Slightly Superexponential Parameterized Problems
• Finding Branch-Decompositions and Rank-Decompositions
• A polynomial kernel for distance-hereditary vertex deletion

This page was built for publication: Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.