A kernel of order 2k - c for Vertex Cover

DOI10.1016/J.DISC.2011.02.014MaRDI QIDQ534063zbMATH OpenOpenAlexFDO

Authors Arezou Soleimanfallah, A. Yeo

Publication date 10 May 2011

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2011.02.014

zbMATH Keywords

kernelvertex coverfixed parameter tractable

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A kernel of order \(2k-c\log k\) for vertex cover
• A 2k-kernelization algorithm for vertex cover based on crown decomposition
• Kernels for structural parameterizations of vertex cover -- case of small degree modulators
• An improved fixed-parameter algorithm for vertex cover
• Crown structures for vertex cover kernelization

Cites work

• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2119538 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Crown reductions for the minimum weighted vertex cover problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Paths, Trees, and Flowers
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex cover: Further observations and further improvements
• Vertex packings: Structural properties and algorithms

Cited in

(12)

• A (2 + ) k-vertex kernel for the dual coloring problem
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Crown structures for vertex cover kernelization
• A kernel of order \(2k-c\log k\) for vertex cover
• scientific article; zbMATH DE number 6857816 (Why is no real title available?)
• Polynomial kernels for vertex cover parameterized by small degree modulators
• A 2k-kernelization algorithm for vertex cover based on crown decomposition
• What Is Known About Vertex Cover Kernelization?
• Computing kernels in parallel: lower and upper bounds
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Kernels for the Vertex Cover Problem on the Preferred Attachment Model
• Polynomial kernels for proper interval completion and related problems

This page was built for publication: A kernel of order \(2k - c\) for Vertex Cover

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