An edge-reduction algorithm for the vertex cover problem

DOI10.1016/j.orl.2009.01.010zbMath1167.90667OpenAlexW1978372231MaRDI QIDQ833573

Qiaoming Han, Yinyu Ye, Abraham P. Punnen

Publication date: 14 August 2009

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

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

zbMATH Keywords

approximation algorithmvertex cover problemLP-relaxation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (1)

Strong and weak edges of a graph and linkages with the vertex cover problem

Cites Work

• Unnamed Item
• Efficient bounds for the stable set, vertex cover and set packing problems
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• The importance of being biased
• On the power of unique 2-prover 1-round games
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Vertex packings: Structural properties and algorithms
• The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
• Vertex Cover Approximations on Random Graphs
• Experimental and Efficient Algorithms
• Automata, Languages and Programming

This page was built for publication: An edge-reduction algorithm for the vertex cover problem