New approximation algorithms for the vertex cover problem

DOI10.1007/978-3-642-45278-9_39MaRDI QIDQ2870054zbMATH OpenOpenAlexFDO

Authors François Delbot, Christian Laforest, Raksmey Phan

Publication date 17 January 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45278-9_39

zbMATH Keywords

approximationlower boundvertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Divide-and-conquer approximation algorithm for vertex cover
• scientific article; zbMATH DE number 3853131
• An edge-reduction algorithm for the vertex cover problem
• On the approximability of the vertex cover and related problems
• Improved approximation of maximum vertex cover

Cited in

(26)

• A graph approximation heuristic for the vertex cover problem on planar graphs
• A new approximation algorithm for k-set cover problem
• Approximation for vertex cover in -conflict graphs
• Vertex cover in conflict graphs
• Experimental analysis of approximation algorithms for the vertex cover and set covering problems
• Improved approximation of maximum vertex cover
• A list heuristic for vertex cover
• scientific article; zbMATH DE number 1594511 (Why is no real title available?)
• Analysis and comparison of three algorithms for the vertex cover problem on large graphs with low memory capacities
• scientific article; zbMATH DE number 3853131 (Why is no real title available?)
• Some results on incremental vertex cover problem
• On the approximability of the vertex cover and related problems
• Divide-and-conquer approximation algorithm for vertex cover
• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• scientific article; zbMATH DE number 2080241 (Why is no real title available?)
• A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set
• An articulation point-based approximation algorithm for minimum vertex cover problem
• Verified approximation algorithms
• Analytical and experimental comparison of six algorithms for the vertex cover problem
• Vertex Cover Approximations on Random Graphs
• Experimental and Efficient Algorithms
• Automata, Languages and Programming
• A (2-)-approximation ratio for vertex cover problem on special graphs
• Improved upper bounds for vertex cover
• On the hardness of approximating minimum vertex cover
• An edge-reduction algorithm for the vertex cover problem

This page was built for publication: New approximation algorithms for the vertex cover problem

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