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.
|Name||Memorandum Afdeling TW|
|Publisher||University of Twente, Department of Applied Mathematics|
- EC Grant Agreement nr.: FP5/34734