Hostname: page-component-8448b6f56d-qsmjn Total loading time: 0 Render date: 2024-04-17T23:36:35.055Z 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)
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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