فهرست نشریات علمی دسترسی آزاد ایران

‎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‎}.