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

crown decompositionFPT algorithmskernelizationNP-completenessvertex cover

Mathematics Subject Classification ID

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

Recommendations

• Crown structures for vertex cover kernelization
• A kernel of order 2k-c 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

• 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
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• 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

(17)

• A kernel of order 2k-c k for vertex cover
• Reoptimization of parameterized problems
• Kernels for packing and covering problems
• Crown structures for vertex cover kernelization
• Crown reductions for the minimum weighted vertex cover problem
• Why is maximum clique often easy in practice?
• Kernels for the Vertex Cover Problem on the Preferred Attachment Model
• Parameterized and Exact Computation
• A kernel of order \(2k - c\) for Vertex Cover
• Graph-Theoretic Concepts in Computer Science
• A polytime preprocess algorithm for the maximum independent set problem
• What Is Known About Vertex Cover Kernelization?
• Total domination and open packing in some subclasses of bipartite graphs
• Combining crown structures for vulnerability measures
• A 1.9999-approximation algorithm for vertex cover on string graphs
• Vertex identification to a forest
• Combining crown structures for vulnerability measures

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)