A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs

Tim Nieberg; Johann Hurink

doi:10.1007/11671411_23

A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs

Tim Nieberg, Johann Hurink

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

47 Citations (Scopus)

Abstract

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.

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	https://doi.org/10.1007/11671411_23
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

Nieberg, T., & Hurink, J. (2006). A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. In T. Erlebach, & G. Persiano (Eds.), Approximation and Online Algorithms: Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers (pp. 296-306). (Lecture Notes in Computer Science; Vol. 3879). Berlin, Heidelberg: Springer. https://doi.org/10.1007/11671411_23

Nieberg, Tim ; Hurink, Johann. / A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. Approximation and Online Algorithms: Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers. editor / Thomas Erlebach ; Giuseppe Persiano. Berlin, Heidelberg : Springer, 2006. pp. 296-306 (Lecture Notes in Computer Science).

@inproceedings{57cbc0d213e642d1811db64a4b8ff7e1,

title = "A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs",

abstract = "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.",

keywords = "EC Grant Agreement nr.: FP5/34734",

author = "Tim Nieberg and Johann Hurink",

year = "2006",

doi = "10.1007/11671411_23",

language = "English",

isbn = "3-540-32207-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "296--306",

editor = "Thomas Erlebach and Giuseppe Persiano",

booktitle = "Approximation and Online Algorithms",

}

Nieberg, T & Hurink, J 2006, A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. in T Erlebach & G Persiano (eds), Approximation and Online Algorithms: Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers. Lecture Notes in Computer Science, vol. 3879, Springer, Berlin, Heidelberg, pp. 296-306, 3rd International Workshop on Approximation and Online Algorithms, WAOA 2005, Palma de Mallorca, Spain, 6/10/05. https://doi.org/10.1007/11671411_23

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 -

Nieberg T, Hurink J. A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. In Erlebach T, Persiano G, editors, Approximation and Online Algorithms: Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers. Berlin, Heidelberg: Springer. 2006. p. 296-306. (Lecture Notes in Computer Science). https://doi.org/10.1007/11671411_23

Access to Document

10.1007/11671411_23