Advertisement
Published in:
2007 | OriginalPaper | Chapter
Online Conflict-Free Colorings for Hypergraphs
Authors : Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky, Shakhar Smorodinsky
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We provide a framework for online conflict-free coloring (CF-coloring) of any hypergraph. We use this framework to obtain an efficient randomized online algorithm for CF-coloring any
k
-degenerate hypergraph. Our algorithm uses
O
(
k
log
n
) colors with high probability and this bound is asymptotically optimal for any constant
k
. Moreover, our algorithm uses
O
(
k
log
k
log
n
) random bits with high probability. As a corollary, we obtain asymptotically optimal randomized algorithms for online CF-coloring some hypergraphs that arise in geometry. Our algorithm uses exponentially fewer random bits compared to previous results.
We introduce deterministic online CF-coloring algorithms for points on the line with respect to intervals and for points on the plane with respect to halfplanes (or unit discs) that use
Θ
(log
n
) colors and recolor
O
(
n
) points in total.