A PTAS for the minimum dominating set problem in unit disk graphs

T. Nieberg, Johann L. Hurink

Research output: Book/ReportReportProfessional

164 Downloads (Pure)

Abstract

We present a polynomial-time approximation scheme (PTAS) for the minimum dominating set problem in unit disk graphs. In contrast to previously known approximation schemes for the minimum dominating set problem on unit disk graphs, our approach does not assume a geometric representation of the vertices (specifying the positions of the disks in the plane) to be given as part of the input.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages14
ISBN (Print)0169-2690
Publication statusPublished - 2004

Publication series

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

Keywords

  • METIS-219688
  • MSC-05R69
  • EWI-3552
  • EC Grant Agreement nr.: FP5/34734
  • IR-65916
  • MSC-05R62
  • MSC-68R10

Cite this

Nieberg, T., & Hurink, J. L. (2004). A PTAS for the minimum dominating set problem in unit disk graphs. (Memorandum Afdeling TW; No. 1732). Enschede: University of Twente, Department of Applied Mathematics.