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

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

44 Citations (Scopus)
68 Downloads (Pure)

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.
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
PublisherSpringer
Pages214-221
Number of pages8
ISBN (Print)3-540-24132-9
DOIs
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
PublisherSpringer-Verlag
Volume3353
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004
Abbreviated titleWG
CountryGermany
CityBad Honnef
Period21/06/0423/06/04

Keywords

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

Cite this