On a Decentralized (Δ+1)-Graph Coloring Algorithm
On a Decentralized (Δ+1)-Graph Coloring Algorithm
复制标题
DOI：
10.1137/1.9781611976014.13
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Deeparnab Chakrabarty;P. D. Supinski
中科院分区：
文献类型：
--
作者：
Deeparnab Chakrabarty;P. D. Supinski
我们考虑一个分散的图着色模型，其中每个顶点只知道它自己的颜色和是否有一些邻居与它具有相同的颜色。网络社区已经广泛地研究了这个模型，因为它应用于信道选择，速率自适应等。在这里，我们分析了Bhartia等人的简单算法的变体[Proc.，ACM MOBIHOC，2016年]。特别是，我们引入了一个变体，它只需要O（nlog Δ）预期的扩展，推广优惠券收集器问题。最后，我们证明了Bhartia等人的算法在对抗场景中的O（nΔ）界仍然成立，并且是紧的。
We consider a decentralized graph coloring model where each vertex only knows its own color and whether some neighbor has the same color as it. The networking community has studied this model extensively due to its applications to channel selection, rate adaptation, etc. Here, we analyze variants of a simple algorithm of Bhartia et al. [Proc., ACM MOBIHOC, 2016]. In particular, we introduce a variant which requires onlyO(nlog Δ) expected recolorings that generalizes the coupon collector problem. Finally, we show that theO(nΔ) bound Bhartia et al. achieve for their algorithm still holds and is tight in adversarial scenarios.