A note on maximum independent sets in rectangle intersection graphs

Research output: Contribution to journalArticle

Abstract

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n2k-1) time bound for any integer constant k≥1; we describe a similar algorithm running in only O(nlogn+nΔk-1) time, where Δ≤n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈logkn⌉-factor algorithm with an O(nk+1) time bound for any integer constant k≥2; we describe similar algorithms running in O(nlogn+nΔk-2) and nO(k/logk) time.

Original languageEnglish (US)
Pages (from-to)19-23
Number of pages5
JournalInformation Processing Letters
Volume89
Issue number1
DOIs
StatePublished - Jan 16 2004
Externally publishedYes

Keywords

  • Approximation algorithms
  • Computational geometry
  • Dynamic programming

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'A note on maximum independent sets in rectangle intersection graphs'. Together they form a unique fingerprint.

  • Cite this