@article { author = {Abam, M.A.}, title = {Tight online conflict-free coloring of intervals}, journal = {Scientia Iranica}, volume = {28}, number = {Special issue on collective behavior of nonlinear dynamical networks}, pages = {1493-1496}, year = {2021}, publisher = {Sharif University of Technology}, issn = {1026-3098}, eissn = {2345-3605}, doi = {10.24200/sci.2020.54600.3826}, abstract = {‎We ‎revisit 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$‎. ‎To best of our knowledge, the ‎best-‎known ‎algorithm ‎uses‎ $O(\log^3 n )$ ‎colors, where $n$ is the number of current intervals‎. ‎We‎ present a simple greedy algorithm that uses only $O(\log n)$ colors. Therefore, we settle down the open problem raised in \cite{ars1‎4‎}.}, keywords = {‎Frequency Assignment‎,‎Conflict-Free Coloring‎,‎Intervals‎,‎On-line Algorithms‎,‎Computational Geometry}, url = {https://scientiairanica.sharif.edu/article_22068.html}, eprint = {https://scientiairanica.sharif.edu/article_22068_c78602be375ed7f3f9d321aa6f47f3f2.pdf} }