A new PTAS for maximum independent sets in unit disk graphs

Research output: Book/ReportReportProfessional

38 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

Nieberg, T., Hurink, J. L., & Kern, W. (2003). A new PTAS for maximum independent sets in unit disk graphs. (Memorandum Afdeling TW; No. 1688). Enschede: University of Twente, Department of Applied Mathematics.
Nieberg, T. ; Hurink, Johann L. ; Kern, Walter. / A new PTAS for maximum independent sets in unit disk graphs. Enschede : University of Twente, Department of Applied Mathematics, 2003. 7 p. (Memorandum Afdeling TW; 1688).
@book{f4267065b2b34182bccd108a86174c5e,
title = "A new PTAS for maximum independent sets in unit disk graphs",
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).",
keywords = "MSC-05C62, IR-65873, METIS-213742, MSC-05C69, EWI-3508, MSC-68R10, MSC-90C35",
author = "T. Nieberg and Hurink, {Johann L.} and Walter Kern",
note = "Imported from MEMORANDA",
year = "2003",
language = "Undefined",
isbn = "0169-2690",
series = "Memorandum Afdeling TW",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1688",

}

Nieberg, T, Hurink, JL & Kern, W 2003, A new PTAS for maximum independent sets in unit disk graphs. Memorandum Afdeling TW, no. 1688, University of Twente, Department of Applied Mathematics, Enschede.

A new PTAS for maximum independent sets in unit disk graphs. / Nieberg, T.; Hurink, Johann L.; Kern, Walter.

Enschede : University of Twente, Department of Applied Mathematics, 2003. 7 p. (Memorandum Afdeling TW; No. 1688).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - A new PTAS for maximum independent sets in unit disk graphs

AU - Nieberg, T.

AU - Hurink, Johann L.

AU - Kern, Walter

N1 - Imported from MEMORANDA

PY - 2003

Y1 - 2003

N2 - 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).

AB - 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).

KW - MSC-05C62

KW - IR-65873

KW - METIS-213742

KW - MSC-05C69

KW - EWI-3508

KW - MSC-68R10

KW - MSC-90C35

M3 - Report

SN - 0169-2690

T3 - Memorandum Afdeling TW

BT - A new PTAS for maximum independent sets in unit disk graphs

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Nieberg T, Hurink JL, Kern W. A new PTAS for maximum independent sets in unit disk graphs. Enschede: University of Twente, Department of Applied Mathematics, 2003. 7 p. (Memorandum Afdeling TW; 1688).