A list heuristic for vertex cover

DOI10.1016/j.orl.2006.03.014zbMath1125.05079OpenAlexW2095553101MaRDI QIDQ2643795

Tomokazu Imamura, David Avis

Publication date: 27 August 2007

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2006.03.014

zbMATH Keywords

approximation algorithmvertex coverlist heuristic

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Vertex degrees (05C07)

Related Items

An Articulation Point-Based Approximation Algorithm for Minimum Vertex Cover Problem ⋮ Unnamed Item ⋮ A better list heuristic for vertex cover ⋮ Mean analysis of an online algorithm for the vertex cover problem ⋮ \(\text{PSPIKE}+\): A family of parallel hybrid sparse linear system solvers ⋮ Priority algorithms for graph optimization problems

Cites Work

• On the ratio of optimal integral and fractional covers
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Unnamed Item