Tight online conflict-free coloring of intervals

Document Type : Article

Author

Department of Computer Engineering, Sharif University of Technology, Tehran, Iran

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

References

References:
[1] Abam, M. A. and Rezaei Seraji, M. J. and Shadravan, M. \Online Conflict-Free Coloring of Intervals, Journal of Scientia Iranica", Journal of Scientia Iranica, 21(6):2138-2141 (2014).
[2] Even, G. and Lotker, Z. and Ron, D. and Smorodinsky, S. \Conflict-freee colorings of simple geo-metric regions with applications to frequency assignment in cellular networks", SIAM J. Comput., 33(1):94-136 (2003).
[3] Har-Peled, S. and Smorodinsky S. \Conflict-Free coloring of points and simple regions in the plane", Discr. Comput. Geom., 34(1):47-70 (2005).
[4] Ashok, P. and Dudeja, A. and Kolay, S. and Saurabh, S. \ Exact and  xed parameter tractable algorithms for max-con
ict-free coloring in hypergraphs", SIAM J. Discrete Math., 32(2):1189-1208 (2018).
[5] Cheilaris, P. and Gargano, L. and Rescigno, A. A. and Smorodinsky, S. \Strong Conflict-Free Coloring for Intervals". Algorithmica, 70(4):732-749 (2014).
[6] Cui, Z. and Hu, Z. \ On variants of conflict-free-coloring for hypergraphs", Discrete Applied Mathematics, 220:46-54 (2017).
[7] Fekete, S. P. and Keldenich, P. \Conflict-free coloring of intersection graphs", International Journal of Computational Geometry and Applications, 28(3):289-307 (2018).
[8] Gargano, L. and Rescigno, A. A. \ Complexity of conflict-free colorings of graphs", Theor. Comput. Sci., 566:39-49 (2015).
6 List of Figures [9] Keller, C. and Smorodinsky, S. \Conflict-Free Coloring of Intersection Graphs of Geometric Objects", In Proc. SODA, pages 2397-2411, 2018.
[10] Reddy, I. V. \Parameterized algorithms for conflict-free colorings of graphs", Theoretical Computer Science, 745:53-62 (2018).
[11] Chen, K. and Fiat, A. and Kaplan, H. and Levy, M. and Matousek, J. and Mossel, E. and Pach, J. and Sharir, M. and Smorodinsky, S. and Wagner, U. and Welzl, E. \Online conflict-free coloring for intervals", SIAM J. Comput., 36(5):1342-1359 (2007).
[12] Pach, J. and Toth, G. \Conflict-free colorings", Discrete and Computational Geometry, The Goodman-Pollack Festschrift, (B. Aronov, S. Basu, J. Pach and M. Sharir, editors), Springer Verlag, Heidelberg, 665{671 (2003).
[13] Bar-Noy, A. and Cheilaris, P. and Smorodinsky, S. \Conflict-free coloring for intervals: from online to online", In Proc. ACM Sympos. on Parallelism Algorithms Architectures, pages 128-137, 2006.
[14] de Berg, M. and Markovic, A. \Dynamic conflict-free colorings in the plane", Comput. Geom., 78:61-73 (2019).
[15] de Berg, M. and Leijsen, T. and Markovic, A. and van Renssen, A. and Roelo zen, M. and Woegin- ger, G. J. \Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points", Int. J. Comput. Geometry Appl. 29(1):49-72 (2019).
Scientia Iranica
Volume 28, Special issue on collective behavior of nonlinear dynamical networks
Transactions on Computer Science & Engineering and Electrical Engineering (D)
June 2021
Pages 1493-1496

Files

History

  • Receive Date: 28 October 2019
  • Revise Date: 06 August 2020
  • Accept Date: 02 November 2020

Share

How to cite

Statistics