A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem

This publication has 13 references indexed in Scilit:

• Improving the performance guarantee for approximate graph coloring
  Journal of the ACM, 1983
• Efficient bounds for the stable set, vertex cover and set packing problems
  Discrete Applied Mathematics, 1983
• Some further approximation algorithms for the vertex cover problem
  Published by Springer Nature ,1983
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
  SIAM Journal on Computing, 1982
• On the Problem of Partitioning Planar Graphs
  SIAM Journal on Algebraic Discrete Methods, 1982
• A linear-time approximation algorithm for the weighted vertex cover problem
  Journal of Algorithms, 1981
• Finding a Minimum Circuit in a Graph
  SIAM Journal on Computing, 1978
• Vertex packings: Structural properties and algorithms
  Mathematical Programming, 1975
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
  SIAM Journal on Computing, 1973
• Reducibility among Combinatorial Problems
  Published by Springer Nature ,1972