On the k-coloring of Intervals

Martin C. Carlisle and Errol Lloyd

May 1991

Abstract The problem of coloring a set of intervals (from the real line) with a set of k colors is studied. In such a coloring, two intervals may have the same color if and only if those intervals do not overlap. Two versions of the problem are considered. For the first, we provide an O(k+n) time algorithm for k-coloring a maximum cardinality subset of the intervals. The best previous algorithm for this problem required time O(kn). In the second version, we assume that each interval has a weight, and provide an O(knlogn) algorithm for k-coloring a set of intervals of maximum total weight. The best previous algorithm for this problem required time O(n^2logn). These results provide improved solutions to problems of local register allocation, task scheduling, and the routing of nets on a chip.

This paper appeared in the Proceedings of the International Conference on Computing and Information, Ottawa, Canada. Also as Springer-Verlag LNCS 497 (pages 90-101), and in journal form in Discrete Applied Mathematics 59(1995) pp. 225-235.