Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.

DOI10.4230/LIPIcs.ESA.2018.48OpenAlexW3043016546MaRDI QIDQ5009611

Bart M. P. Jansen, Astrid Pieterse

Publication date: 4 August 2021

Full work available at URL: https://doi.org/10.4230/LIPIcs.ESA.2018.48

zbMATH Keywords

kernelizationstructural parameterizationtreedepth modulator\(\mathcal{F}\)-minor free deletion

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (3)

Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kernelization using structural parameters on sparse graph classes
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Sparsity. Graphs, structures, and algorithms
• Infeasibility of instance compression and succinct PCPs for NP
• Graph minors. V. Excluding a planar graph
• Vertex Cover Structural Parameterization Revisited
• Uniform Kernelization Complexity of Hitting Forbidden Minors
• Vertex packings: Structural properties and algorithms
• On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Structural Parameterizations of Feedback Vertex Set
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Representative Sets and Irrelevant Vertices
• A Faster Parameterized Algorithm for Treedepth

This page was built for publication: Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.