An edge-reduction algorithm for the vertex cover problem

DOI10.1016/J.ORL.2009.01.010MaRDI QIDQ833573zbMATH OpenOpenAlexFDO

Authors Qiaoming Han, Abraham P. Punnen, Yinyu Ye

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)

Recommendations

• Divide-and-conquer approximation algorithm for vertex cover
• New approximation algorithms for the vertex cover problem
• On the approximability of the vertex cover and related problems
• scientific article; zbMATH DE number 19175
• Strong and weak edges of a graph and linkages with the vertex cover problem

Cites work

• scientific article; zbMATH DE number 2119717 (Why is no real title available?)
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Automata, Languages and Programming
• Efficient bounds for the stable set, vertex cover and set packing problems
• Experimental and Efficient Algorithms
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• On the power of unique 2-prover 1-round games
• The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
• The importance of being biased
• Vertex Cover Approximations on Random Graphs
• Vertex packings: Structural properties and algorithms

Cited in

(18)

• A graph approximation heuristic for the vertex cover problem on planar graphs
• Experimental and Efficient Algorithms
• An articulation point-based approximation algorithm for minimum vertex cover problem
• An approximation algorithm for the minimum weighted vertex-cover problem
• On the approximability of the vertex cover and related problems
• New approximation algorithms for the vertex cover problem
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Vertex Cover Approximations on Random Graphs
• Approximation Algorithms for Edge-Covering Problem
• Strong and weak edges of a graph and linkages with the vertex cover problem
• An approximation of the minimum vertex cover in a graph
• scientific article; zbMATH DE number 3943843 (Why is no real title available?)
• scientific article; zbMATH DE number 3959477 (Why is no real title available?)
• Divide-and-conquer approximation algorithm for vertex cover
• A \((2-\varepsilon)\)-approximation ratio for vertex cover problem on special graphs
• scientific article; zbMATH DE number 3853131 (Why is no real title available?)
• Solving NP-hard problems in 'almost trees': vertex cover
• Some results on incremental vertex cover problem

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

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