A note on maximum independent sets in rectangle intersection graphs |
| |
Authors: | Timothy M Chan |
| |
Affiliation: | School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada |
| |
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. |
| |
Keywords: | Approximation algorithms Computational geometry Dynamic programming |
本文献已被 ScienceDirect 等数据库收录! |
|