Academic
Publications
Online Conflict-Free Colouring for Hypergraphs

Online Conflict-Free Colouring for Hypergraphs,10.1017/S0963548309990587,Combinatorics, Probability & Computing,AMOTZ BAR-NOYy,Panagiotis Cheilaris,Sv

Online Conflict-Free Colouring for Hypergraphs   (Citations: 8)
BibTex | RIS | RefWorks Download
We provide a framework for online conict-free coloring any hypergraph. We intro- duce the notion of degenerate hypergraph, which characterizes hypergraphs that arise in geometry. We use our framework to obtain an ecient randomized online algorithm for conict-free coloring any k-degenerate hypergraph with n vertices. Our algorithm uses O(k logn) colors with high probability and this bound is asymptotically optimal, because there are families ofk-degenerate hypergraphs that need that many colors. Moreover, our algorithm uses O(k logk logn) random bits with high probabil- ity. As a corollary, we obtain asymptotically optimal randomized algorithms for online conict-free coloring some hypergraphs that arise in geometry. Our algorithm uses exponentially fewer random bits than previous algorithms. We introduce algorithms that are allowed to perform a few recolorings of already colored points. We provide deterministic online conict-free coloring algorithms for points on the line with respect to intervals and for points on the plane with respect to halfplanes (or unit disks) that use O(logn) colors and perform number of recolorings at most linear in n.
Journal: Combinatorics, Probability & Computing - CPC , vol. 19, no. 4, pp. 493-516, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...An even more recent result of Bar-Noy, Cheilaris, and Smorodinsky [3] provides a general randomized online CF coloring algorithm, which achieves the same performance as [6] in the special cases just mentioned...
    • ...(a) Theorem 6.1 and the initial encouraging results of Chen, Kaplan, and Sharir [6] and of Bar-Noy, Cheilaris, and Smorodinsky [3], as reviewed in the introduction, raise many interesting open problems, such as the following: (i) Obtain deterministic algorithms with good performance for the cases studied in [6], viz...

    Ke Chenet al. Online Conflict-Free Coloring for Intervals

    • ...An even more recent result of Bar Noy et al. [4] provides a general randomized online CF-coloring algorithm, which achieves the same performance as [7] in the special cases just mentioned...
    • ...(a) Theorem 6.1, and the initial encouraging results of Chen, Kaplan and Sharir [7] and of Bar Noy et al. [4], as reviewed in the introduction, raise many interesting open problems, such as: (i) Obtain deterministic algorithms with good performance for the cases studied in [7], viz...

    N. Goodwin. Online Conflict-Free Coloring for Intervals 1

    • ...An even more recent result of Bar Noy et al. [4] provides a general randomized online CF-coloring algorithm, which achieves the same performance as [7] in the special cases just mentioned...
    • ...(a) Theorem 6.1, and the initial encouraging results of Chen, Kaplan and Sharir [7] and of Bar Noy et al. [4], as reviewed in the introduction, raise many interesting open problems, such as: (i) Obtain deterministic algorithms with good performance for the cases studied in [7], viz...

    Amos Fiatet al. Online conflict-free coloring for intervals

Sort by: