|
|||||
|
|
A linear-time approximation algorithm for the weighted vertex cover problem |
|
| Authors: | R Bar-Yehuda S Even |
| Affiliation: | Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel |
| Abstract: | A linear time approximation algorithm for the weighted set-covering problem is presented. For the special case of the weighted vertex cover problem it produces a solution of weight which is at most twice the weight of an optimal solution. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |