Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/1813
Title: Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
Authors: Erlebach, Thomas
Jansen, Klaus
Seidel, Eike
First Published: 2005
Citation: SIAM Journal on Computing, 2005, 34 (6), pp.1302-1323
Abstract: A disk graph is the intersection graph of a set of disks with arbitrary diameters in the plane. For the case that the disk representation is given, we present polynomial-time approximation schemes (PTASs) for the maximum weight independent set problem (selecting disjoint disks of maximum total weight) and for the minimum weight vertex cover problem in disk graphs. These are the first known PTASs for $\mathcal{NP}$-hard optimization problems on disk graphs. They are based on a novel recursive subdivision of the plane that allows applying a shifting strategy on different levels simultaneously, so that a dynamic programming approach becomes feasible. The PTASs for disk graphs represent a common generalization of previous results for planar graphs and unit disk graphs. They can be extended to intersection graphs of other "disk-like" geometric objects (such as squares or regular polygons), also in higher dimensions.
DOI Link: 10.1137/S0097539702402676
ISSN: 0097-5397
Links: http://epubs.siam.org/doi/abs/10.1137/S0097539702402676
http://hdl.handle.net/2381/1813
Type: Article
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
There are no files associated with this item.


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.