The paper considers the geometric conflict-free coloring problem, introduced in [G. Even, Z. Lotker, D. Ron, S. Smorodinsky, Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks, SIAM J. Comput. 33 (2003) 94-133]. The input of this problem is a set of regions in the plane and the output is an assignment of colors to the regions, such that for every point p in the total coverage area, there exist a color i and a region D such that P E D, the region D is colored i, and every other region D' that contains p is not colored i. The target is to minimize the number of colors used. This problem arises from issues of frequency assignment in radio networks. The paper presents an O(1) approximation algorithm for the conflict-free coloring problem where the regions are unit disks.
展开▼
机译：本文考虑了在[G. Even，Z. Lotker，D. Ron，S. Smorodinsky，简单几何区域的无冲突着色及其在蜂窝网络中的频率分配应用，SIAM J. Comput。 33（2003）94-133]。这个问题的输入是平面中的一组区域，而输出是这些区域的颜色分配，因此对于总覆盖区域中的每个点p，都存在颜色i和区域D，从而使PED，区域D被着色为i，而其他每个包含p的区域D'都不被着色为i。目标是尽量减少使用的颜色数量。该问题是由无线电网络中的频率分配问题引起的。针对区域为单位圆盘的无冲突着色问题，本文提出了一种O（1）近似算法。
展开▼
