TY - JOUR
ID - 3607
TI - Online conflict-free coloring of intervals
JO - Scientia Iranica
JA - SCI
LA - en
SN - 1026-3098
AU - Abam, M.A.
AU - Rezaei Seraji, M.J.
AU - Shadravan, M.
AD - Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
Y1 - 2014
PY - 2014
VL - 21
IS - 6
SP - 2138
EP - 2141
KW - Frequency assignment
KW - Conflict-free coloring
KW - Intervals
KW - On-line algorithms
KW - Computational geometry
DO -
N2 - 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
UR - http://scientiairanica.sharif.edu/article_3607.html
L1 - http://scientiairanica.sharif.edu/article_3607_437db4a9645b9db91954fd85067f04d2.pdf
ER -