A PTAS for the minimum dominating set problem in unit disk graphs

Share/Save/Bookmark

Nieberg, Tim and Hurink, Johann (2004) A PTAS for the minimum dominating set problem in unit disk graphs. [Report]

open access
[img]
Preview
PDF
216kB
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

 

Repository Staff Only: item control page

Metis ID: 219688