A kernel of order \(2k - c\) for Vertex Cover

DOI10.1016/j.disc.2011.02.014zbMath1223.05242OpenAlexW1605363403MaRDI QIDQ534063

Anders Yeo, Arezou Soleimanfallah

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)

Related Items

Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, What Is Known About Vertex Cover Kernelization?, A kernel of order \(2k-c\log k\) for vertex cover, Unnamed Item, Polynomial Kernels for Proper Interval Completion and Related Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Crown reductions for the minimum weighted vertex cover problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex Cover: Further Observations and Further Improvements
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Vertex packings: Structural properties and algorithms
• On the Complexity of Timetable and Multicommodity Flow Problems
• Paths, Trees, and Flowers