Abstract
| Original language | English |
|---|---|
| Title of host publication | Approximation and Online Algorithms |
| Subtitle of host publication | Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers |
| Editors | Thomas Erlebach, Giuseppe Persiano |
| Place of Publication | Berlin, Heidelberg |
| Publisher | Springer |
| Pages | 296-306 |
| Number of pages | 11 |
| ISBN (Electronic) | 978-3-540-32208-5 |
| ISBN (Print) | 3-540-32207-8 |
| DOIs | |
| Publication status | Published - 2006 |
| Event | 3rd International Workshop on Approximation and Online Algorithms, WAOA 2005 - Hotel Tryp Bellver, Palma de Mallorca, Spain Duration: 6 Oct 2005 → 7 Oct 2005 Conference number: 3 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 3879 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Workshop
| Workshop | 3rd International Workshop on Approximation and Online Algorithms, WAOA 2005 |
|---|---|
| Abbreviated title | WAOA |
| Country | Spain |
| City | Palma de Mallorca |
| Period | 6/10/05 → 7/10/05 |
Fingerprint
Keywords
- EC Grant Agreement nr.: FP5/34734
Cite this
}
A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. / Nieberg, Tim; Hurink, Johann.
Approximation and Online Algorithms: Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers. ed. / Thomas Erlebach; Giuseppe Persiano. Berlin, Heidelberg : Springer, 2006. p. 296-306 (Lecture Notes in Computer Science; Vol. 3879).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
TY - GEN
T1 - A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs
AU - Nieberg, Tim
AU - Hurink, Johann
PY - 2006
Y1 - 2006
N2 - We present a polynomial-time approximation scheme (PTAS) for the minimum dominating set problem in unit disk graphs. In contrast to previously known approximation schemes for the minimum dominating set problem on unit disk graphs, our approach does not assume a geometric representation of the vertices (specifying the positions of the disks in the plane) to be given as part of the input. The runtime of the PTAS is n O(1/εlog 1/ε). The algorithm accepts any undirected graph as input, and returns a (1 + ε)-approximate minimum dominating set, or a certificate showing that the input graph is no unit disk graph, making the algorithm robust. The PTAS can easily be adapted to other classes of geometric intersection graphs.
AB - We present a polynomial-time approximation scheme (PTAS) for the minimum dominating set problem in unit disk graphs. In contrast to previously known approximation schemes for the minimum dominating set problem on unit disk graphs, our approach does not assume a geometric representation of the vertices (specifying the positions of the disks in the plane) to be given as part of the input. The runtime of the PTAS is n O(1/εlog 1/ε). The algorithm accepts any undirected graph as input, and returns a (1 + ε)-approximate minimum dominating set, or a certificate showing that the input graph is no unit disk graph, making the algorithm robust. The PTAS can easily be adapted to other classes of geometric intersection graphs.
KW - EC Grant Agreement nr.: FP5/34734
U2 - 10.1007/11671411_23
DO - 10.1007/11671411_23
M3 - Conference contribution
SN - 3-540-32207-8
T3 - Lecture Notes in Computer Science
SP - 296
EP - 306
BT - Approximation and Online Algorithms
A2 - Erlebach, Thomas
A2 - Persiano, Giuseppe
PB - Springer
CY - Berlin, Heidelberg
ER -