A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition

DOI10.1016/j.tcs.2018.05.004zbMath1395.68154OpenAlexW2802677919MaRDI QIDQ1643162

Binhai Zhu, Wenjun Li

Publication date: 18 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.05.004

zbMATH Keywords

NP-completenessvertex coverkernelizationFPT algorithmscrown decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Reoptimization of parameterized problems ⋮ A polytime preprocess algorithm for the maximum independent set problem ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Kernels for packing and covering problems

Cites Work

• Unnamed Item
• Unnamed Item
• Improved upper bounds for vertex cover
• An improved kernelization algorithm for \(r\)-set packing
• A kernelization algorithm for \(d\)-hitting set
• An improved kernelization for \(P_{2}\)-packing
• Towards optimal kernel for edge-disjoint triangle packing
• Crown structures for vertex cover kernelization
• Parametrized complexity theory.
• Vertex packings: Structural properties and algorithms
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition