Advertisement
Published in:
2006 | OriginalPaper | Chapter
A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs
Authors : Tim Nieberg, Johann Hurink
Published in: Approximation and Online Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.