论文标题
充血中有效的随机分布着色
Efficient Randomized Distributed Coloring in CONGEST
论文作者
论文摘要
分布式顶点着色是经典问题之一，也可能是分布式图算法领域中研究最广泛的问题。我们为标准的通讯模型提供了一种新的随机分布式顶点着色算法，该算法将网络建模为$ n $ node graph $ g $，其中$ g $的节点在同步通信弹中运行，他们可以在其中交换$ o（\ log n）$ - 在所有$ g $ g $ $ g $的范围上。对于具有最高度$δ$的图表，我们表明$（δ+1）$ - 列表着色问题（因此，标准$（δ+1）$ - 着色问题）可以在$ O（\ log^5 \ log n）$ rounds中解决。以前，这种结果仅因强大的本地模型而闻名，在每个回合中，相邻节点可以交换任意大小的消息。最佳的先前$（δ+ 1）$ - coled模型中的着色算法的运行时间为$ O（\logΔ+ \ log^6 \ log n）$ rounds。因此，作为$ n $的函数，最好的以前算法的复杂性为$ o（\ log n）$，这是一个幼稚的民俗算法也可以实现的界限。对于大型$δ$，我们的算法是对先前最新状态的指数改进。
Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomized distributed vertex coloring algorithm for the standard CONGEST model, where the network is modeled as an $n$-node graph $G$, and where the nodes of $G$ operate in synchronous communication rounds in which they can exchange $O(\log n)$-bit messages over all the edges of $G$. For graphs with maximum degree $Δ$, we show that the $(Δ+1)$-list coloring problem (and therefore also the standard $(Δ+1)$-coloring problem) can be solved in $O(\log^5\log n)$ rounds. Previously such a result was only known for the significantly more powerful LOCAL model, where in each round, neighboring nodes can exchange messages of arbitrary size. The best previous $(Δ+1)$-coloring algorithm in the CONGEST model had a running time of $O(\logΔ+ \log^6\log n)$ rounds. As a function of $n$ alone, the best previous algorithm therefore had a round complexity of $O(\log n)$, which is a bound that can also be achieved by a naïve folklore algorithm. For large maximum degree $Δ$, our algorithm hence is an exponential improvement over the previous state of the art.
