Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235617] of Pankaj K. Agarwal

Papers Published

  1. 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. 127-137, ISSN 0302-9743
    (last updated on 2018/12/17)

    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 NP-complete 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. © Springer-Verlag Berlin Heidelberg 2004.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320