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


Nieberg, Tim and Hurink, Johann (2006) A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. In: 3rd International Workshop on Approximation and Online Algorithms, WAOA 2005, 6-7 October 2005, Palma de Mallorca, Spain (pp. pp. 296-306).

[img] PDF
Restricted to UT campus only
: Request a copy
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.
Item Type:Conference or Workshop Item
Copyright:© 2006 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62840
Official URL:http://dx.doi.org/10.1007/11671411_23
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 239250