A kernel of order \(2k-c\log k\) for vertex cover
From MaRDI portal
Publication:1944208
DOI10.1016/j.ipl.2011.09.003zbMath1260.05165OpenAlexW2016639462MaRDI QIDQ1944208
Publication date: 4 April 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2011.09.003
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Parameterized Power Vertex Cover ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ A polynomial kernel for 3-leaf power deletion ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression
Cites Work
- Unnamed Item
- A kernel of order \(2k - c\) for Vertex Cover
- Almost 2-SAT is fixed-parameter tractable
- Crown reductions for the minimum weighted vertex cover problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Parametrized complexity theory.
- Vertex Cover: Further Observations and Further Improvements
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- On Multiway Cut Parameterized above Lower Bounds
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Vertex packings: Structural properties and algorithms
- Paths, Trees, and Flowers
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
This page was built for publication: A kernel of order \(2k-c\log k\) for vertex cover