A new PTAS for maximum independent sets in unit disk graphs

T. Nieberg, Johann L. Hurink, Walter Kern

Research output: Book/ReportReportProfessional

71 Downloads (Pure)

Abstract

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).
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages7
ISBN (Print)0169-2690
Publication statusPublished - 2003

Publication series

NameMemorandum Afdeling TW
PublisherUniversity of Twente, Department of Applied Mathematics
No.1688
ISSN (Print)0169-2690

Keywords

  • MSC-05C62
  • IR-65873
  • METIS-213742
  • MSC-05C69
  • EWI-3508
  • MSC-68R10
  • MSC-90C35

Cite this