Coloring unit-disk graphs efficiently is an important problem in the global and distributed setting, with applications in radio channel assignment problems when the communication relies on omni-directional antennas of the same power. In this context it is important to bound not only the complexity of the coloring algorithms, but also the number of colors used. In this paper, we consider two natural distributed settings. In the location-aware setting (when nodes know their coordinates in the plane), we give a constant time distributed algorithm coloring any unit-disk graph $G$ with at most $(3+\epsilon)\omega(G)+6$ colors, for any constant $\epsilon>0$, where $\omega(G)$ is the clique number of $G$. This improves upon a classical 3-approximation algorithm for this problem, for all unit-disk graphs whose chromatic number significantly exceeds their clique number. When nodes do not know their coordinates in the plane, we give a distributed algorithm in the LOCAL model that colors every unit-disk graph $G$ with at most $5.68\omega(G)$ colors in $O(2^{\sqrt{\log \log n}})$ rounds. Moreover, when $\omega(G)=O(1)$, the algorithm runs in $O(\log^* n)$ rounds. This algorithm is based on a study of the local structure of unit-disk graphs, which is of independent interest. We conjecture that every unit-disk graph $G$ has average degree at most $4\omega(G)$, which would imply the existence of a $O(\log n)$ round algorithm coloring any unit-disk graph $G$ with (approximatively) $4\omega(G)$ colors.
翻译:高效的彩色单位- disk 图形是全球和分布式设置中的一个重要问题, 当通信依赖于同一电力的全向天线时, 无线电频道分配应用程序中的应用程序存在问题。 在此情况下, 不仅要约束颜色算法的复杂性, 还要约束所使用的颜色数量。 在本文中, 我们考虑两种自然分布的设置 。 在定位设置中( 当节点知道其在平面上的坐标时), 我们给出一个固定时间分布的算法, 任何单位- disk 图形$G$( 3 ⁇ epsilon)\ omega( G)+6$的颜色, 对于任何恒定的 $( eepsilon) 0$, 其中$\ omga( G) 是 clocal= $G 的圆数数。 对于所有单位- a- a- addrink 的色数图形, 我们给出一个分布式的算法 $G=== 美元单位- 美元 美元单位的数值。