A kernel of order 2k - c for Vertex Cover
From MaRDI portal
Publication:534063
DOI10.1016/J.DISC.2011.02.014zbMATH Open1223.05242OpenAlexW1605363403MaRDI QIDQ534063FDOQ534063
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
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
- Paths, Trees, and Flowers
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Vertex packings: Structural properties and algorithms
- On the Complexity of Timetable and Multicommodity Flow Problems
- Title not available (Why is that?)
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Title not available (Why is that?)
- Crown reductions for the minimum weighted vertex cover problem
- Vertex cover: Further observations and further improvements
Cited In (11)
- A \((2 + \epsilon ) 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Polynomial Kernels for Proper Interval Completion and Related Problems
- What Is Known About Vertex Cover Kernelization?
- Kernels for the Vertex Cover Problem on the Preferred Attachment Model
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
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)
