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.
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)
|Link to this item:||http://purl.utwente.nl/publications/65547|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page
Metis ID: 219609