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. |
Year | DOI | Venue |
---|---|---|
1981 | 10.1016/0196-6774(81)90020-1 | Journal of Algorithms |
Keywords | Field | DocType |
vertex cover,linear time | Approximation algorithm,Discrete mathematics,Combinatorics,Edge cover,Prim's algorithm,Vertex cover,Time complexity,Feedback vertex set,Mathematics,Special case,Vertex model | Journal |
Volume | Issue | ISSN |
2 | 2 | 0196-6774 |
Citations | PageRank | References |
182 | 38.27 | 1 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Reuven Bar-Yehuda | 1 | 1492 | 189.18 |
shimon even | 2 | 2873 | 981.78 |