Math @ Duke

Publications [#235617] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Mustafa, NH, Independent set of intersection graphs of convex objects in 2D,
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3111
(2004),
pp. 127137, ISSN 03029743
(last updated on 2018/09/22)
Abstract: The intersection graph of a set of geometric objects is defined as a graph G = (S, E) in which there is an edge between two nodes si, sj ∈ S if si ∩ sj ≠ ∅. The problem of computing a maximum independent set in the intersection graph of a set of objects is known to be NPcomplete for most cases in two and higher dimensions. We present approximation algorithms for computing a maximum independent set of intersection graphs of convex objects in ℝ2. Specifically, given a set of n line segments in the plane with maximum independent set of size κ, we present algorithms that find an independent set of size at least (i) (κ/2 log(2n/κ))1/2 in time O(n3) and (ii) (κ/2 log(2n/κ))1/4 in time O(n4/3 logc n). For a set of n convex objects with maximum independent set of size κ, we present an algorithm that finds an independent set of size at least (κ/2 log(2n/κ))1/3 in time O(n3+τ(S)), assuming that S can be preprocessed in time τ(S) to answer certain primitive operations on these convex sets. © SpringerVerlag Berlin Heidelberg 2004.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

