Preprocessing for treewidth: a combinatorial analysis through kernelization

DOI10.1137/120903518MaRDI QIDQ5408612zbMATH OpenOpenAlexWikidataFDO

Authors 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

kernelizationparameterized complexitypreprocessingtreewidth

Mathematics Subject Classification ID

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

Recommendations

• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Preprocessing subgraph and minor problems: when does a small vertex cover help?

Cited in

(25)

• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Meta-kernelization using well-structured modulators
• FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
• Clique Cover and Graph Separation
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Treewidth computation and kernelization in the parallel external memory model
• Treewidth and pathwidth parameterized by the vertex cover number
• scientific article; zbMATH DE number 1953092 (Why is no real title available?)
• Confronting intractability via parameters
• Computing kernels in parallel: lower and upper bounds
• Hans Bodlaender and the Theory of Kernelization Lower Bounds
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• The Power of Linear-Time Data Reduction for Maximum Matching
• Degree-3 treewidth sparsifiers
• Approximate Turing Kernelization for Problems Parameterized by Treewidth
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• Slim tree-cut width
• A graph searching game for block treedepth and a cubic kernel by vertex cover
• Search-space reduction via essential vertices
• Computing twin-width parameterized by the feedback edge number
• Computing twin-width parameterized by the feedback edge number and vertex integrity
• Slim tree-cut width
• A safeness condition for minimal separators based on vertex connectivity
• Twin-width meets feedback edges and vertex integrity
• Meta-kernelization with structural parameters

This page was built for publication: Preprocessing for treewidth: a combinatorial analysis through kernelization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408612)