Abstract
We consider the \(k\)-strong conflict-free (\(k\)-SCF) coloring of a set of points on a line with respect to a family of intervals: Each point on the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval \(I\) of the family there are at least \(k\) colors each appearing exactly once in \(I\). We first present a polynomial-time approximation algorithm for the general problem; the algorithm has approximation ratio 2 when \(k=1\) and \(5-\frac{2}{k}\) when \(k\ge 2\). In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any \(k \ge 1\). We also provide, in case \(k=O({{\mathrm{polylog}}}(n))\), a quasipolynomial time algorithm to decide the existence of a \(k\)-SCF coloring that uses at most \(q\) colors.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Unless otherwise specified, all logarithms are in base 2.
References
Abam, M.A., de Berg, M., Poon, S.H.: Fault-tolerant conflict-free coloring. In: Proc. 20th Canadian Conference on Computational Geometry (CCCG) (2008)
Abellanas, M., Bose, P., Garcia, J., Hurtado, F., Nicolas, M., Ramos, P.A.: On properties of higher order Delaunay graphs with applications. In: Proc. 21st European Workshop on Computational Geometry (EWCG), pp. 119–122 (2005)
Bar-Noy, A., Cheilaris, P., Olonetsky, S., Smorodinsky, S.: Online conflict-free colouring for hypergraphs. Comb. Probab. Comput. 19, 493–516 (2010)
Bar-Noy, A., Cheilaris, P., Smorodinsky, S.: Deterministic conflict-free coloring for intervals: from offline to online. ACM Trans. Algorithms 4(4), 44 (2008)
Chen, K., Fiat, A., Levy, M., Matoušek, J., Mossel, E., Pach, J., Sharir, M., Smorodinsky, S., Wagner, U., Welzl, E.: Online conflict-free coloring for intervals. SIAM J. Comput. 36, 545–554 (2006)
Chen, K., Kaplan, H., Sharir, M.: Online conflict free coloring for congruent disks, and axis-parallel rectangles. ACM Trans. Algorithms 5(2) (2009). doi:10.1145/1497290.1497292
Cui, Z., Hu, Z.C.: \(k\)-conflict-free coloring and \(k\)-strong-conflict-free coloring for one class of hypergraphs and online \(k\)-conflict-free coloring (2011). arXiv:1107.0138
Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33, 94–136 (2003)
Horev, E., Krakovski, R., Smorodinsky, S.: Conflict-free coloring made stronger. In: Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 105–117 (2010)
Katz, M., Lev-Tov, N., Morgenstern, G.: Conflict-free coloring of points on a line with respect to a set of intervals. Comput. Geom. 45, 508–514 (2012)
Lev-Tov, N., Peleg, D.: Conflict-free coloring of unit disks. Discrete Appl. Math. 157(7), 1521–1532 (2009)
Nguyen, H.L., Nguyen, U.T.: Algorithms for bandwidth efficient multicast routing in multi-channel multi-radio wireless mesh networks. In: Proc. IEEE Wireless Communications and Networking Conference (WCNC), pp. 1107–1112 (2011)
Papadimitriou, C.: Computational Complexity. Addison Wesley, Boston (1993)
Smorodinsky, S.: Conflict-free coloring and its applications (2010). arXiv:1005.3616
Zeng, G., Wang, B., Ding, Y., Xiao, L., Mutka, M.: Efficient multicast algorithms for multichannel wireless mesh networks. IEEE Trans. Parallel Distrib. Syst. 21, 86–99 (2010)
Acknowledgments
We are grateful to the anonymous reviewers for their comments and suggestions, which significantly helped us improve the quality of the paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cheilaris, P., Gargano, L., Rescigno, A.A. et al. Strong Conflict-Free Coloring for Intervals. Algorithmica 70, 732–749 (2014). https://doi.org/10.1007/s00453-014-9929-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-014-9929-x