• 35 Citations

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 languageUndefined
Title of host publication3rd International Workshop on Approximation and Online Algorithms, WAOA 2005
EditorsThomas Erlebach, Giuseppe Persiano
Place of PublicationHeidelberg, Germany
PublisherSpringer Verlag
Pages296-306
Number of pages11
ISBN (Print)3-540-32207-8
DOIs
StatePublished - 2006
Event3rd International Workshop on Approximation and Online Algorithms 2005 - Palma de Mallorca, Spain

Publication series

NameLecture Notes in Computer Science
PublisherSpringer-Verlag
Volume3879
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop3rd International Workshop on Approximation and Online Algorithms 2005
Abbreviated titleWAOA 2005
CountrySpain
CityPalma de Mallorca
Period6/10/057/10/05

Fingerprint

Unit disk graph
Polynomial time approximation scheme
Dominating set
Geometric graphs
Geometric representation
Intersection graphs
Robust algorithm
Certificate
Approximation scheme
Undirected graph
Graph in graph theory

Keywords

  • EC Grant Agreement nr.: FP5/34734
  • IR-62840
  • METIS-239250
  • EWI-1685

Cite this

Nieberg, T., & Hurink, J. L. (2006). A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. In T. Erlebach, & G. Persiano (Eds.), 3rd International Workshop on Approximation and Online Algorithms, WAOA 2005 (pp. 296-306). [10.1007/11671411_23] (Lecture Notes in Computer Science; Vol. 3879). Heidelberg, Germany: Springer Verlag. DOI: 10.1007/11671411_23

Nieberg, T.; Hurink, Johann L. / A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs.

3rd International Workshop on Approximation and Online Algorithms, WAOA 2005. ed. / Thomas Erlebach; Giuseppe Persiano. Heidelberg, Germany : Springer Verlag, 2006. p. 296-306 10.1007/11671411_23 (Lecture Notes in Computer Science; Vol. 3879).

Research output: Scientific - peer-reviewConference contribution

@inbook{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, IR-62840, METIS-239250, EWI-1685",
author = "T. Nieberg and Hurink, {Johann L.}",
year = "2006",
doi = "10.1007/11671411_23",
isbn = "3-540-32207-8",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "296--306",
editor = "Thomas Erlebach and Giuseppe Persiano",
booktitle = "3rd International Workshop on Approximation and Online Algorithms, WAOA 2005",

}

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

A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. / Nieberg, T.; Hurink, Johann L.

3rd International Workshop on Approximation and Online Algorithms, WAOA 2005. ed. / Thomas Erlebach; Giuseppe Persiano. Heidelberg, Germany : Springer Verlag, 2006. p. 296-306 10.1007/11671411_23 (Lecture Notes in Computer Science; Vol. 3879).

Research output: Scientific - peer-reviewConference contribution

TY - CHAP

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

AU - Nieberg,T.

AU - Hurink,Johann L.

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

KW - IR-62840

KW - METIS-239250

KW - EWI-1685

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 - 3rd International Workshop on Approximation and Online Algorithms, WAOA 2005

PB - Springer Verlag

ER -

Nieberg T, Hurink JL. A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. In Erlebach T, Persiano G, editors, 3rd International Workshop on Approximation and Online Algorithms, WAOA 2005. Heidelberg, Germany: Springer Verlag. 2006. p. 296-306. 10.1007/11671411_23. (Lecture Notes in Computer Science). Available from, DOI: 10.1007/11671411_23