%0 Journal Article
%T Online conflict-free coloring of intervals
%J Scientia Iranica
%I Sharif University of Technology
%Z 1026-3098
%A Abam, M.A.
%A Rezaei Seraji, M.J.
%A Shadravan, M.
%D 2014
%\ 12/01/2014
%V 21
%N 6
%P 2138-2141
%! Online conflict-free coloring of intervals
%K Frequency assignment
%K Conflict-free coloring
%K Intervals
%K On-line algorithms
%K Computational geometry
%R
%X In this paper, we study the problem of online conflict-free coloring of intervals on a line, where each newly inserted interval must be assigned a color upon insertion such that the coloring remains conflict-free, i.e. for each point p in the union of the current intervals, there must be an interval I with a unique color among all intervals covering p. We first present a simple algorithm which uses O(pn) colors where n is the number of current intervals. Next, we propose an CF-coloring of intervals which uses O(log3 n) colors
%U http://scientiairanica.sharif.edu/article_3607_437db4a9645b9db91954fd85067f04d2.pdf