A new PTAS for maximum independent sets in unit disk graphs
Tim Nieberg, Johann L. Hurink, Walter Kern · University of Twente Research Information · 2003
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).