|
|||||
|
|
An edge-reduction algorithm for the vertex cover problem |
|
| Authors: | Qiaoming Han Yinyu Ye |
| Affiliation: | a School of Mathematics and Statistics, Zhejiang University of Finance and Economics, Hangzhou 310018, PR China b Department of Mathematics, Simon Fraser University, 14th Floor Central City Tower, 13450 102nd Ave., Surrey, BC V3T5X3, Canada c Department of Management Science and Engineering, School of Engineering, Stanford University, Stanford, CA 94305, USA |
| Abstract: | An approximation algorithm for the vertex cover problem is proposed with performance ratio  on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S1 such that  where S∗ is an optimal cover and ξ is an error bound identified. |
| Keywords: | Vertex cover problem Approximation algorithm LP-relaxation |
| 本文献已被 ScienceDirect 等数据库收录！ | |