Name
Abstract | ||
|---|---|---|
We study the problem of finding a minimal edge dominating set of maximum size in a given graph G = (V, E), called UPPER EDS. We show that this problem is not approximable within a ratio of n(epsilon-1/2), for any epsilon is an element of (0, 1/2), assuming P not equal NP, where n = vertical bar V vertical bar. On the other hand, for graphs of minimum degree at least 2, we give an approximation algorithm with ratio 1/root n, matching this lower bound. We further show that UPPER EDS is APX-complete in bipartite graphs of maximum degree 4, and NP-hard in planar bipartite graphs of maximum degree 4. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.tcs.2021.03.038 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
Edge dominating set, NP-completeness, Approximability | Journal | 877 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jérôme Monnot | 1 | 512 | 55.74 |
| Henning Fernau | 2 | 1646 | 162.68 |
| David F. Manlove | 3 | 761 | 60.45 |