A new PTAS for maximum independent sets in unit disk graphs

Share/Save/Bookmark

Nieberg, Tim and Hurink, Johann and Kern, Walter (2003) A new PTAS for maximum independent sets in unit disk graphs. [Report]

[img]
Preview
PDF
97Kb
Abstract:A unit disk graph is an intersection graph of unit disks in the euclidean plane. We present a polynomial-time approximation scheme for the maximum independent set problem in unit disk graphs. In contrast to previously known approximation schemes, our approach does not require a geometric representation (specifying the coordinates of the disk centers).
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65873
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 213742