| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142837 | Operations Research Letters | 2009 | 6 Pages |
Abstract
An approximation algorithm for the vertex cover problem is proposed with performance ratio 32 on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S1S1 such that |S1|≤32|S∗|+ξ where S∗S∗ is an optimal cover and ξξ is an error bound identified.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Qiaoming Han, Abraham P. Punnen, Yinyu Ye,