Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
From MaRDI portal
Publication:5092404
DOI10.4230/LIPIcs.MFCS.2019.42MaRDI 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
68Qxx: Theory of computing
Related Items
On the Parameterized Complexity of Clique Elimination Distance, Measuring what matters: a hybrid approach to dynamic programming with treewidth, Solving projected model counting by utilizing treewidth and its limits
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