A list heuristic for vertex cover

DOI10.1016/J.ORL.2006.03.014MaRDI QIDQ2643795zbMATH OpenOpenAlexFDO

Authors 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 algorithmlist heuristicvertex cover

Mathematics Subject Classification ID

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

Review text

A class of approximation algorithms for the minimum vertex cover problem for graphs is studied. These algorithms, called list heuristics, handle the vertices in a given static order based on the degree sequence. The authors prove an approximation ratio of at most \(\sqrt{\Delta}/2+\frac{3}{2}\) for a nonincreasing degree sequence, and show that no ordering can guarantee an approximation ratio of less than \(\sqrt{\Delta}/2\), where \(\Delta\) is the maximum degree.

Recommendations

• On approximation of the vertex cover problem in hypergraphs
• scientific article; zbMATH DE number 3853131
• Analytical and experimental comparison of six algorithms for the vertex cover problem
• New approximation algorithms for the vertex cover problem
• Divide-and-conquer approximation algorithm for vertex cover

Cites work

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

Cited in

(9)

• Priority algorithms for graph optimization problems
• Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
• scientific article; zbMATH DE number 1953099 (Why is no real title available?)
• An articulation point-based approximation algorithm for minimum vertex cover problem
• A (2-)-approximation ratio for vertex cover problem on special graphs
• Vertex cover number in diverse graph architectures
• \(\text{PSPIKE}+\): A family of parallel hybrid sparse linear system solvers
• A better list heuristic for vertex cover
• Mean analysis of an online algorithm for the vertex cover problem

This page was built for publication: A list heuristic for vertex cover

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