Vertex Cover Approximations on Random Graphs

DOI10.1007/978-3-540-72845-0_22MaRDI QIDQ5432321zbMATH OpenOpenAlexFDO

Authors Eyjólfur Ingi Ásgeirsson, Clifford Stein

Publication date 2 January 2008

Published in Experimental Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-72845-0_22

Mathematics Subject Classification ID

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

Recommendations

• Divide-and-conquer approximation algorithm for vertex cover
• Experimental and Efficient Algorithms
• New approximation algorithms for the vertex cover problem
• An edge-reduction algorithm for the vertex cover problem
• On the approximability of the vertex cover and related problems

Cited in

(12)

• A probabilistic estimator for the vertex deletion problem
• Solving vertex cover in polynomial time on hyperbolic random graphs
• Approximating vertex cover on dense graphs
• Minimum vertex cover in generalized random graphs with power law degree distribution
• Typical performance of approximation algorithms for NP-hard problems
• Divide-and-conquer approximation algorithm for vertex cover
• Greedy Local Search and Vertex Cover in Sparse Random Graphs
• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• Experimental and Efficient Algorithms
• A (2-)-approximation ratio for vertex cover problem on special graphs
• Strong and weak edges of a graph and linkages with the vertex cover problem
• An edge-reduction algorithm for the vertex cover problem

This page was built for publication: Vertex Cover Approximations on Random Graphs

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