Preprocessing subgraph and minor problems: When does a small vertex cover help?

DOI10.1007/978-3-642-33293-7_11MaRDI QIDQ4899244zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Bart M. P. Jansen, Michał Pilipczuk

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-33293-7_11

Mathematics Subject Classification ID

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

Recommendations

• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F}\)-minor-free deletion
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
• Hitting forbidden minors: approximation and kernelization
• Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel

Cited in

(4)

• Maximum common induced subgraph parameterized by vertex cover
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels

This page was built for publication: Preprocessing subgraph and minor problems: When does a small vertex cover help?

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