| A note on maximum independent sets in rectangle intersection graphs (2004) | |||||||||||||||||
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 (1997) gave a (1+1=k)-factor algorithm with an O(n log n + n 2k 1) time bound for any integer constant k 1; we describe a similar algorithm running in only O(n log n + 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 (2001) gave a dlog k ne-factor algorithm with an O(n k+1) time bound for any integer constant k 2; we describe similar algorithms running in O(n log n + n k 2) and n O(k = log k) time. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||