| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652629 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
We study the approximability of subdense instances of various covering optimization problems, including Vertex Cover, Connected Vertex Cover, Set Cover, and Steiner Tree problems. In those instances, the minimum (or average) degree of the underlying graph is o(n), but Ω(n/ψ(n)) for some function ψ of the number n of vertices. We design new approximation algorithms or new polynomial time approximation schemes (PTAS) for those problems and establish the first approximation hardness results for some of them.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
