Online Conflict-Free Colouring for Hypergraphs
Online Conflict-Free Colouring for Hypergraphs
复制标题
DOI：
10.1017/s0963548309990587
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
A. Bar-Noy;Panagiotis Cheilaris;Svetlana Olonetsky;Shakhar Smorodinsky
中科院分区：
文献类型：
--
作者：
A. Bar-Noy;Panagiotis Cheilaris;Svetlana Olonetsky;Shakhar Smorodinsky
我们为任何超图的在线无冲突着色提供了一个框架。我们引入了退化超图的概念，它刻画了几何中出现的超图。利用我们的框架，我们得到了任意n个顶点的k-退化超图的无冲突着色的一个有效的随机在线算法。我们的算法使用了高概率的O(Klogn)色，并且这个界是渐近最优的。此外，该算法高概率地使用O(Klogklogn)个随机比特。我们引入了一些算法，允许对已经着色的点执行几次重新着色。我们为直线上的点相对于区间和平面上的点相对于半平面(或单位圆盘)提供了确定性的在线无冲突着色算法，这些算法使用O(Logn)色，总共至多执行O(N)次再着色。
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.