Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

DOI10.1137/120903518zbMath1290.05143OpenAlexW2070685861WikidataQ59567517 ScholiaQ59567517MaRDI QIDQ5408612

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

Publication date: 10 April 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/120903518

zbMATH Keywords

treewidthparameterized complexitykernelizationpreprocessing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Hans Bodlaender and the Theory of Kernelization Lower Bounds ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ Clique Cover and Graph Separation ⋮ Meta-kernelization using well-structured modulators ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ Meta-kernelization with structural parameters ⋮ Unnamed Item ⋮ Confronting intractability via parameters ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ FPT is characterized by useful obstruction sets ⋮ The Power of Linear-Time Data Reduction for Maximum Matching ⋮ On sparsification for computing treewidth

This page was built for publication: Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization