Measuring what matters: a hybrid approach to dynamic programming with treewidth
type: Item
instance of: scholarly article
title: Measuring what matters: a hybrid approach to dynamic programming with treewidth
author: Eduard Eiben
author: Robert Ganian
author: Thekla Hamm
author: O-joung Kwon
published in: Journal of Computer and System Sciences
publication date: 2021-07-06T00:00:00Z
full work available at URL: https://arxiv.org/abs/1908.10132
Mathematics Subject Classification ID: 68-XX
zbMATH DE Number: 7368162
zbMATH Keywords: parameterized complexity
zbMATH Keywords: treewidth
zbMATH Keywords: rank-width
zbMATH Keywords: fixed-parameter algorithms
MaRDI profile type: Publication
OpenAlex ID: W3162608353
cites work: Q3888545
cites work: Graph classes with structured neighborhoods and algorithmic applications
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: (Meta) Kernelization
cites work: Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
cites work: Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
cites work: Reduction algorithms for graphs of small treewidth
cites work: How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
cites work: Graph isomorphism parameterized by elimination distance to bounded degree
cites work: Fixed-parameter tractable distances to sparse graph classes
cites work: Parameterized complexity of vertex colouring
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Q3077955
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Upper bounds to the clique width of graphs
cites work: Vertex-minors, monadic second-order logic, and a conjecture by Seese
cites work: Fast Hamiltonicity Checking Via Bases of Perfect Matchings
cites work: Q4947393
cites work: Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
cites work: Fundamentals of parameterized complexity
cites work: Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
cites work: A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
cites work: Meta-kernelization using well-structured modulators
cites work: Solving problems on graphs of high rank-width
cites work: Deciding Clique-Width for Graphs of Bounded Tree-Width
cites work: Graph Layout Problems Parameterized by Vertex Cover
cites work: Parametrized complexity theory.
cites work: Intractability of Clique-Width Parameterizations
cites work: Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
cites work: Preprocessing subgraph and minor problems: when does a small vertex cover help?
cites work: Kernelization using structural parameters on sparse graph classes
cites work: Q3455032
cites work: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
cites work: A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
cites work: Backdoor treewidth for SAT
cites work: Combining Treewidth and Backdoors for CSP.
cites work: Meta-kernelization with structural parameters
cites work: Finding Branch-Decompositions and Rank-Decompositions
cites work: Which problems have strongly exponential complexity?
cites work: Mim-width. II. The feedback vertex set problem
cites work: Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
cites work: Generalized coloring for tree-like graphs
cites work: The rank-width of the square grid
cites work: Maximum matching width: new characterizations and a fast algorithm for dominating set
cites work: An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
cites work: A polynomial kernel for distance-hereditary vertex deletion
cites work: Treewidth. Computations and approximations
cites work: Edge dominating set and colorings on graphs with fixed clique-width
cites work: Q4381404
cites work: Slightly Superexponential Parameterized Problems
cites work: Immersions in Highly Edge Connected Graphs
cites work: Q5710169
cites work: Rank-width and vertex-minors
cites work: Approximating clique-width and branch-width
cites work: Graph minors. III. Planar tree-width
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Between treewidth and clique-width
cites work: Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
DOI: 10.1016/J.JCSS.2021.04.005
description: scientific article; zbMATH DE number 7368162