Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs
verfasst von : Tim Nieberg, Johann Hurink
Erschienen in: Approximation and Online Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.