A robust PTAS for maximum independent sets in unit disk graphs


Nieberg, Tim and Hurink, Johann and Kern, Walter (2004) A robust PTAS for maximum independent sets in unit disk graphs. In: 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, 21-23 June 2004, Bad Honnef, Germany (pp. pp. 214-221).

[img] PDF
Restricted to UT campus only
: Request a copy
Abstract:A unit disk graph is the intersection graph of unit disks in the euclidean plane. We present a polynomial-time approximation scheme for the maximum weight 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).
The approximation algorithm presented is robust in the sense that it accepts any graph as input and either returns a (1+)-approximate independent set or a certificate showing that the input graph is no unit disk graph. The algorithm can easily be extended to other families of intersection graphs of geometric objects.
Item Type:Conference or Workshop Item
Copyright:© 2004 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65547
Official URL:https://doi.org/10.1007/978-3-540-30559-0_18
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 219609