An edge-reduction algorithm for the vertex cover problem
From MaRDI portal
Publication:833573
DOI10.1016/J.ORL.2009.01.010zbMATH Open1167.90667OpenAlexW1978372231MaRDI QIDQ833573FDOQ833573
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
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
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Cites Work
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Vertex packings: Structural properties and algorithms
- The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
- On the power of unique 2-prover 1-round games
- Vertex Cover Approximations on Random Graphs
- Efficient bounds for the stable set, vertex cover and set packing problems
- Experimental and Efficient Algorithms
- The importance of being biased
- Automata, Languages and Programming
- Title not available (Why is that?)
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
- Title not available (Why is that?)
- An approximation of the minimum vertex cover in a graph
- Title not available (Why is that?)
- Divide-and-conquer approximation algorithm for vertex cover
- A \((2-\varepsilon)\)-approximation ratio for vertex cover problem on special graphs
- Title not available (Why is that?)
- 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)
