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

Tim Nieberg, Johann Hurink

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

69 Citations (Scopus)
3 Downloads (Pure)

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 languageEnglish
Title of host publicationApproximation and Online Algorithms
Subtitle of host publicationThird International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers
EditorsThomas Erlebach, Giuseppe Persiano
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages296-306
Number of pages11
ISBN (Electronic)978-3-540-32208-5
ISBN (Print)3-540-32207-8
DOIs
Publication statusPublished - 2006
Event3rd International Workshop on Approximation and Online Algorithms, WAOA 2005 - Hotel Tryp Bellver, Palma de Mallorca, Spain
Duration: 6 Oct 20057 Oct 2005
Conference number: 3

Publication series

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

Workshop

Workshop3rd International Workshop on Approximation and Online Algorithms, WAOA 2005
Abbreviated titleWAOA
Country/TerritorySpain
CityPalma de Mallorca
Period6/10/057/10/05

Keywords

  • EC Grant Agreement nr.: FP5/34734

Fingerprint

Dive into the research topics of 'A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs'. Together they form a unique fingerprint.

Cite this