Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

DOI10.1007/978-3-642-22006-7_37zbMath1333.68204arXiv1104.4217OpenAlexW2128049247WikidataQ59567614 ScholiaQ59567614MaRDI QIDQ3012824

Stefan Kratsch, Bart M. P. Jansen, Hans L. Bodlaender

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1104.4217

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal, On the Hardness of Losing Width, On Cutwidth Parameterized by Vertex Cover, New Limits to Classical and Quantum Instance Compression, Kernelization – Preprocessing with a Guarantee, Fixed-Parameter Tractability of Treewidth and Pathwidth, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Preprocessing subgraph and minor problems: when does a small vertex cover help?, Dual parameterization and parameterized approximability of subset graph problems, On the hardness of losing width, On cutwidth parameterized by vertex cover, Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization, Kernelization hardness of connectivity problems in \(d\)-degenerate graphs, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Safe separators for treewidth
• Safe reduction rules for weighted treewidth
• On problems without polynomial kernels
• Computing the treewidth and the minimum fill-in with the modular decomposition
• Necessary edges in \(k\)-chordalisations of graphs
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Complexity of Finding Embeddings in a k-Tree
• The Pathwidth and Treewidth of Cographs
• Contraction and Treewidth Lower Bounds
• Heuristic and metaheuristic methods for computing graph treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth