Back to University of Twente portal
A PTAS for the minimum dominating set problem in unit disk graphs
Nieberg, Tim and Hurink, Johann (2004) A PTAS for the minimum dominating set problem in unit disk graphs. [Report]
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 211Kb |
| 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.
|
| Item Type: | Report |
| Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |
| Research Group: | |
| Link to this item: | http://purl.utwente.nl/publications/65916 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page
Metis ID: 219688