Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
From MaRDI portal
Publication:3012824
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
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
