A new PTAS for maximum independent sets in unit disk graphs

T. Nieberg; Johann L. Hurink; Walter Kern

A new PTAS for maximum independent sets in unit disk graphs

T. Nieberg, Johann L. Hurink, Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Book/Report › Report › Professional

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 language	Undefined
Place of Publication	Enschede
Publisher	University of Twente, Department of Applied Mathematics
Number of pages	7
ISBN (Print)	0169-2690
Publication status	Published - 2003

Publication series

Name	Memorandum Afdeling TW
Publisher	University 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

Access to Document

Cite this

@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",

}

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 -