On approximating minimum vertex cover for graphs with perfect matching Academic Article

abstract

• 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. 2005 Elsevier B.V. All rights reserved.

authors

• Chen, Jianer

published proceedings

• Theoretical Computer Science

author list (cited authors)

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

citation count

• 6

complete list of authors

• Chen, Jianer||Kanj, Iyad A

publication date

• June 2005

publisher

• Elsevier  Publisher

published in

• Theoretical Computer Science  Journal

Digital Object Identifier (DOI)

• 10.1016/j.tcs.2004.12.034

start page

• 305

end page

• 318

volume

• 337

issue

• 1-3

URL

• http://dx.doi.org/10.1016/j.tcs.2004.12.034