Name
Abstract | ||
|---|---|---|
We address the max min vertex cover problem, which is the maximization version of the well studied min independent dominating set problem, known to be NP -hard and highly inapproximable in polynomial time. We present tight approximation results for this problem on general graphs, namely a polynomial approximation algorithm which guarantees an¿ n - 1 2 approximation ratio, while showing that unless P = NP , the problem is inapproximable within ratio¿ n ε - ( 1 2 ) for any strictly positive¿ ε . We also analyze the problem on various restricted classes of graphs, on which we show polynomiality or constant-approximability of the problem. Finally, we show that the problem is fixed-parameter tractable with respect to the size of an optimal solution, to treewidth and to the size of a maximum matching. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.dam.2014.06.001 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Max min vertex cover,Min independent dominating set,Polynomial approximation,Inapproximability,Parametric complexity | Discrete mathematics,Approximation algorithm,Dominating set,Combinatorics,Edge cover,Chordal graph,Matching (graph theory),Vertex cover,Treewidth,Time complexity,Mathematics | Conference |
Volume | Issue | ISSN |
196 | C | 0166-218X |
Citations | PageRank | References |
6 | 0.53 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Boria | 1 | 59 | 7.23 |
| Federico Della Croce | 2 | 399 | 41.60 |
| Vangelis Th. Paschos | 3 | 633 | 63.97 |