On approximating minimum vertex cover for graphs with perfect matching Conference Paper

abstract

• Springer-Verlag Berlin Heidelberg 2000. It has been a challenging open problem whether there is a polynomial time approximation algorithm for the Vertex Cover problem whose approximation ratio is bounded by a constant less than 2. In this paper, we study the Vertex Cover problem on graphs with perfect matching (shortly, VC-PM). We show that if the VC-PM problem has a polynomial time approximation algorithm with approximation ratio bounded by a constant less than 2, then so does the Vertex Cover problem on general graphs. Approximation algorithms for VC-PM are developed, which induce improvements over previously known algorithms on sparse graphs. For example, for graphs of average degree 5, the approximation ratio of our algorithm is 1:414, compared with the previously best ratio 1:615 by Halldrsson and Radhakrishnan.

name of conference

• Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18-20, 2000, Proceedings

authors

• Chen, Jianer

published proceedings

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

• Chen, J., & Kanj, I. A.

complete list of authors

• Chen, J||Kanj, IA

publication date

• January 2000

published in

• Lecture Notes in Artificial Intelligence  Journal

International Standard Book Number (ISBN) 10

• 3540412557

International Standard Book Number (ISBN) 13

• 9783540412557

start page

• 132

end page

• 143

volume

• 1969