论文标题
磁盘图的在线着色
Online coloring of disk graphs
论文作者
论文摘要
在本文中，我们为在线算法提供了一系列的在线算法，用于圆盘直径的圆盘相交图的经典着色问题。我们的算法利用了此类图的几何表示，并受到Fiala等人的算法的启发，但具有更好的竞争比率。改进来自在对顶点进行涂色之前使用两种分区的技术。其中一种是平面b折的应用。该方法更为笼统，我们展示了如何将其应用于平面上的其他形状，并为在线L（2，1）标签调整它。
In this paper, we give a family of online algorithms for the classical coloring problem of intersection graphs of discs with bounded diameter. Our algorithms make use of a geometric representation of such graphs and are inspired by an algorithm of Fiala et al., but have better competitive ratios. The improvement comes from using two techniques of partitioning the set of vertices before coloring them. One of whichis an application of a b-fold coloring of the plane. The method is more general and we show how it can be applied to coloring other shapes on the plane as well as adjust it for online L(2, 1)-labeling.
