Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T09:14:48.158Z Has data issue: false hasContentIssue false
  • English
  • Français

Online Conflict-Free Colouring for Hypergraphs

Published online by Cambridge University Press:  11 December 2009

A. BAR-NOY ,
P. CHEILARIS ,
S. OLONETSKY  and
S. SMORODINSKY
A. BAR-NOY
Affiliation:
Computer and Information Science Department, Brooklyn College, USA (e-mail: amotz@sci.brooklyn.cuny.edu)
P. CHEILARIS
Affiliation:
Center for Advanced Studies in Mathematics, Ben-Gurion University, Israel (e-mail: panagiot@math.bgu.ac.il)
S. OLONETSKY
Affiliation:
School of Computer Science, Tel-Aviv University, Israel (e-mail: olonetsk@post.tau.ac.il)
S. SMORODINSKY
Affiliation:
Department of Mathematics, Ben-Gurion University, Israel (e-mail:shakhar@math.bgu.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We provide a framework for online conflict-free colouring of any hypergraph. We introduce the notion of a degenerate hypergraph, which characterizes hypergraphs that arise in geometry. We use our framework to obtain an efficient randomized online algorithm for conflict-free colouring of any k-degenerate hypergraph with n vertices. Our algorithm uses O(k log n) colours with high probability and this bound is asymptotically optimal. Moreover, our algorithm uses O(k log k log n) random bits with high probability. We introduce algorithms that are allowed to perform a few recolourings of already coloured points. We provide deterministic online conflict-free colouring algorithms for points on the line with respect to intervals and for points on the plane with respect to half-planes (or unit disks) that use O(log n) colours and perform a total of at most O(n) recolourings.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 4 , July 2010 , pp. 493 - 516
Copyright
Copyright © Cambridge University Press 2009

References

[1]Ajwani, D., Elbassioni, K., Govindarajan, S. and Ray, S. (2007) Conflict-free coloring for rectangle ranges using O(n .382) colors. In Proc. 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 181–187.Google Scholar
[2]Bar-Noy, A., Cheilaris, P. and Smorodinsky, S. (2006) Conflict-free coloring for intervals: From offline to online. In Proc. 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 128–137.Google Scholar
[3]Bar-Noy, A., Cheilaris, P. and Smorodinsky, S. (2008) Deterministic conflict-free coloring for intervals: From offline to online. ACM Trans. Algorithms 4 44:1–44:18.CrossRefGoogle Scholar
[4]Borodin, A. and El-Yaniv, R. (1998) Online Computation and Competitive Analysis, Cambridge University Press.Google Scholar
[5]Chan, J., Chin, F., Hong, X. and Ting, H. (2008) Dynamic offline conflict-free coloring for unit disks. In Proc. 6th Workshop on Approximation and Online Algorithms (WAOA), pp. 241–252.Google Scholar
[6]Cheilaris, P. (2008) Conflict-free coloring. PhD thesis, City University of New York.Google Scholar
[7]Chen, K. (2006) How to play a coloring game against a color-blind adversary. In Proc. 22nd Annual ACM Symposium on Computational Geometry (SoCG), pp. 44–51.Google Scholar
[8]Chen, K., Fiat, A., Kaplan, H., Levy, M., Matoušek, J., Mossel, E., Pach, J., Sharir, M., Smorodinsky, S., Wagner, U. and Welzl, E. (2007) Online conflict-free coloring for intervals. SIAM J. Comput. 36 1342–1359.CrossRefGoogle Scholar
[9]Chen, K., Kaplan, H. and Sharir, M. (2009) Online conflict free coloring for halfplanes, congruent disks, and axis-parallel rectangles. ACM Trans. Algorithms 5 16:1–16:24.CrossRefGoogle Scholar
[10]Elbassioni, K. and Mustafa, N. H. (2006) Conflict-free colorings of rectangles ranges. In Proc. 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 254–263.Google Scholar
[11]Even, G., Lotker, Z., Ron, D. and Smorodinsky, S. (2003) Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33 94–136.CrossRefGoogle Scholar
[12]Fiat, A., Levy, M., Matoušek, J., Mossel, E., Pach, J., Sharir, M., Smorodinsky, S., Wagner, U. and Welzl, E. (2005) Online conflict-free coloring for intervals. In Proc. 16th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 545–554.Google Scholar
[13]Gyárfás, A. and Lehel, J. (1988) On-line and first fit coloring of graphs. J. Graph Theory 12 217–227.CrossRefGoogle Scholar
[14]Har-Peled, S. and Smorodinsky, S. (2005) Conflict-free coloring of points and simple regions in the plane. Discrete Comput. Geometry 34 47–70.CrossRefGoogle Scholar
[15]Irani, S. (1994) Coloring inductive graphs on-line. Algorithmica 11 53–72.CrossRefGoogle Scholar
[16]Katz, M. J., Lev-Tov, N. and Morgenstern, G. (2007) Conflict-free coloring of points on a line with respect to a set of intervals. In Proc. 19th Canadian Conference on Computational Geometry (CCCG), pp. 93–96.Google Scholar
[17]Kierstead, H. A. (1988) The linearity of first-fit coloring of interval graphs. SIAM J. Discrete Math. 1 526–530.CrossRefGoogle Scholar
[18]Pach, J. and Tóth, G. (2003) Conflict free colorings. In Discrete and Computational Geometry, The Goodman–Pollack Festschrift, Springer, pp. 665–671.CrossRefGoogle Scholar
[19]Schiermeyer, I., Tuza, Z. and Voigt, M. (2000) On-line rankings of graphs. Discrete Math. 212 141–147.CrossRefGoogle Scholar
[20]Smorodinsky, S. (2003) Combinatorial problems in computational geometry. PhD thesis, School of Computer Science, Tel-Aviv University.Google Scholar
[21]Smorodinsky, S. (2007) On the chromatic number of geometric hypergraphs. SIAM J. Discrete Math. 21 676–687.CrossRefGoogle Scholar
[22]Smorodinsky, S. (2008) A note on the online first-fit algorithm for coloring k-inductive graphs. Inform. Process. Lett. 109 44–45.CrossRefGoogle Scholar