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

T. Nieberg; Johann L. Hurink; Walter Kern

doi:10.1007/978-3-540-30559-0_18

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

T. Nieberg
, Johann L. Hurink
, Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

52 Citations (Scopus)

454 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 language	Undefined
Title of host publication	Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004
Editors	Juraj Hromkovič, Manfred Nagel, Bernhard Westfechtel
Place of Publication	Berlin
Publisher	Springer
Pages	214-221
Number of pages	8
ISBN (Print)	3-540-24132-9
DOIs	https://doi.org/10.1007/978-3-540-30559-0_18
Publication status	Published - 2004
Event	30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004 - Bad Honnef, Germany Duration: 21 Jun 2004 → 23 Jun 2004 Conference number: 30

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer-Verlag
Volume	3353
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004
Abbreviated title	WG
Country/Territory	Germany
City	Bad Honnef
Period	21/06/04 → 23/06/04

Keywords

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

Access to Document

10.1007/978-3-540-30559-0_18

ptas_mis

Cite this

Nieberg, T., Hurink, J. L., & Kern, W. (2004). A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs. In J. Hromkovič, M. Nagel, & B. Westfechtel (Eds.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004 (pp. 214-221). Article 10.1007/b104584 (Lecture Notes in Computer Science; Vol. 3353). Springer. https://doi.org/10.1007/978-3-540-30559-0_18

@inproceedings{145e72087dac47aa8ad2134713662fd4,

title = "A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs",

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

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

author = "T. Nieberg and Hurink, \{Johann L.\} and Walter Kern",

year = "2004",

doi = "10.1007/978-3-540-30559-0\_18",

language = "Undefined",

isbn = "3-540-24132-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "214--221",

editor = "Juraj Hromkovi{\v c} and Manfred Nagel and Bernhard Westfechtel",

booktitle = "Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004",

address = "Germany",

note = "30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004 ; Conference date: 21-06-2004 Through 23-06-2004",

}

Nieberg, T, Hurink, JL & Kern, W 2004, A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs. in J Hromkovič, M Nagel & B Westfechtel (eds), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004., 10.1007/b104584, Lecture Notes in Computer Science, vol. 3353, Springer, Berlin, pp. 214-221, 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, Bad Honnef, Germany, 21/06/04. https://doi.org/10.1007/978-3-540-30559-0_18

A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs. / Nieberg, T.; Hurink, Johann L.; Kern, Walter.
Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004. ed. / Juraj Hromkovič; Manfred Nagel; Bernhard Westfechtel. Berlin: Springer, 2004. p. 214-221 10.1007/b104584 (Lecture Notes in Computer Science; Vol. 3353).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Nieberg, T.

AU - Hurink, Johann L.

AU - Kern, Walter

N1 - Conference code: 30

PY - 2004

Y1 - 2004

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

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

KW - METIS-219609

KW - EWI-1784

KW - CAES-PS: Pervasive Systems

KW - EC Grant Agreement nr.: FP5/34734

KW - IR-65547

U2 - 10.1007/978-3-540-30559-0_18

DO - 10.1007/978-3-540-30559-0_18

M3 - Conference contribution

SN - 3-540-24132-9

T3 - Lecture Notes in Computer Science

SP - 214

EP - 221

BT - Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004

A2 - Hromkovič, Juraj

A2 - Nagel, Manfred

A2 - Westfechtel, Bernhard

PB - Springer

CY - Berlin

T2 - 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004

Y2 - 21 June 2004 through 23 June 2004

ER -