On the k-coloring of intervals

On the k-coloring of intervals

0.00 Avg rating0 Votes
Article ID: iaor1997998
Country: Netherlands
Volume: 59
Issue: 3
Start Page Number: 225
End Page Number: 235
Publication Date: May 1995
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: computational analysis
Abstract:

The problem of coloring a set of n intervals (from the real line) with a set of k colors is studied. In such a coloring, two intersecting intervals must receive distinct colors. The present main result is an O(k+n) algorithm for k-coloring a maximum cradinality subset of the intervals, assuming that the endpoints of the intervals are presorted. Previous methods are linear only in n, and assume that k is a fixed constant. In addition to the main result, the authors provide an O(kS(n)) algorithm for k-coloring a set of weighted intervals of maximum total weight. Here, S(n) is the running time of any algorithm for finding shortest paths in graphs with O(n) edges. The best previous algorithm for this problem required time O(nS(n)). Since in most applications, k is substantially smaller than n, the saving is significant.

Reviews

Required fields are marked *. Your email address will not be published.