A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs

T. Nieberg, Johann L. Hurink, Walter Kern

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

49 Citations (Scopus)
116 Downloads (Pure)


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.
Original languageUndefined
Title of host publicationGraph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004
EditorsJuraj Hromkovič, Manfred Nagel, Bernhard Westfechtel
Place of PublicationBerlin
Number of pages8
ISBN (Print)3-540-24132-9
Publication statusPublished - 2004
Event30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004 - Bad Honnef, Germany
Duration: 21 Jun 200423 Jun 2004
Conference number: 30

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Workshop30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004
Abbreviated titleWG
CityBad Honnef


  • METIS-219609
  • EWI-1784
  • CAES-PS: Pervasive Systems
  • EC Grant Agreement nr.: FP5/34734
  • IR-65547

Cite this