A robust PTAS for maximum weight independent sets in unit disk graphs
Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG …, 2005•Springer
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 …
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 …
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.
Springer