Measuring what matters: a hybrid approach to dynamic programming with treewidth
From MaRDI portal
Publication:2040028
DOI10.1016/j.jcss.2021.04.005OpenAlexW3162608353MaRDI QIDQ2040028
O-joung Kwon, Thekla Hamm, Robert Ganian, Eduard Eiben
Publication date: 6 July 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1908.10132
Related Items
A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ FPT algorithms to compute the elimination distance to bipartite graphs and more
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Between treewidth and clique-width
- Graph isomorphism parameterized by elimination distance to bounded degree
- Kernelization using structural parameters on sparse graph classes
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Fundamentals of parameterized complexity
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Graph classes with structured neighborhoods and algorithmic applications
- Graph minors. III. Planar tree-width
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Meta-kernelization with structural parameters
- The rank-width of the square grid
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Graph minors. X: Obstructions to tree-decomposition
- Treewidth. Computations and approximations
- Generalized coloring for tree-like graphs
- Which problems have strongly exponential complexity?
- 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
- Mim-width. II. The feedback vertex set problem
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
- Fixed-parameter tractable distances to sparse graph classes
- Maximum matching width: new characterizations and a fast algorithm for dominating set
- Meta-kernelization using well-structured modulators
- Parametrized complexity theory.
- Approximating clique-width and branch-width
- Rank-width and vertex-minors
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Cluster Vertex Deletion: A Parameterization between Vertex Cover 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.
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Immersions in Highly Edge Connected Graphs
- Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
- Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- 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
