On some approximation algorithms for dense vertex cover problem

MaRDI QIDQ2712300zbMATH OpenFDO

Authors Anton Valentinovich Eremeev

Publication date 6 May 2001

zbMATH Keywords

approximationvertex cover problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximating vertex cover on dense graphs
• scientific article; zbMATH DE number 1163714
• Approximating the dense set-cover problem
• New approximation algorithms for the vertex cover problem
• Approximating vertex cover in dense hypergraphs

Cited in

(10)

• Improved approximation bounds for edge dominating set in dense graphs
• Approximating the dense set-cover problem
• Improved non-approximability results for minimum vertex cover with density constraints
• Runtime analysis of RLS and (1 + 1) EA for the dynamic weighted vertex cover problem
• Approximating vertex cover on dense graphs
• scientific article; zbMATH DE number 1163714 (Why is no real title available?)
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• On hard instances of approximate vertex cover
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• Improved non-approximability results for vertex cover with density constraints

This page was built for publication: On some approximation algorithms for dense vertex cover problem

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