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

DOI10.1016/J.TCS.2018.05.004MaRDI QIDQ1643162zbMATH OpenOpenAlexFDO

Authors Wen-Jun Li, Binhai Zhu

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

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

Recommendations

• Crown structures for vertex cover kernelization
• A kernel of order \(2k-c\log k\) for vertex cover
• A kernel of order \(2k - c\) for Vertex Cover
• Crown reductions for the minimum weighted vertex cover problem
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• A kernelization algorithm for \(d\)-hitting set
• An improved kernelization algorithm for \(r\)-set packing
• An improved kernelization for \(P_{2}\)-packing
• Crown structures for vertex cover kernelization
• Graph-Theoretic Concepts in Computer Science
• Improved upper bounds for vertex cover
• Parametrized complexity theory.
• Towards optimal kernel for edge-disjoint triangle packing
• Vertex packings: Structural properties and algorithms

Cited in

(12)

• Crown structures for vertex cover kernelization
• Crown reductions for the minimum weighted vertex cover problem
• A kernel of order \(2k-c\log k\) for vertex cover
• A polytime preprocess algorithm for the maximum independent set problem
• Graph-Theoretic Concepts in Computer Science
• What Is Known About Vertex Cover Kernelization?
• Parameterized and Exact Computation
• Kernels for the Vertex Cover Problem on the Preferred Attachment Model
• A kernel of order \(2k - c\) for Vertex Cover
• Reoptimization of parameterized problems
• Kernels for packing and covering problems
• Why is maximum clique often easy in practice?

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

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