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).
|Name||Memorandum Afdeling TW|
|Publisher||University of Twente, Department of Applied Mathematics|