Efficient randomized distributed coloring in CONGEST
Efficient randomized distributed coloring in CONGEST
复制标题
CONGEST 中的高效随机分布式着色
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Tigran Tonoyan
中科院分区：
文献类型：
--
作者：
Magn'us M. Halld'orsson;F. Kuhn;Yannic Maus;Tigran Tonoyan
分布式顶点着色是分布式图算法中的经典问题之一，也是研究最多的问题。我们提出了一个新的随机分布顶点着色算法的标准CONGEST模型，其中的网络被建模为一个n-节点图G，和G的节点在同步通信轮，其中他们可以交换O（logn）位的消息在所有的G的边缘。对于最大度为Δ的图，我们证明了（Δ+1）-列表着色问题（因此也是标准的（Δ+1）-着色问题）可以在O（log 5logn）轮内解决。在此之前，这样的结果只适用于功能更强大的以太网模型，在该模型中，在每一轮中，相邻节点可以交换任意大小的消息。CONGEST模型中最好的前（Δ+1）着色算法的运行时间为O（logΔ + log 6logn）轮。作为n的单独函数，最好的先前算法因此具有O（logn）的轮复杂度，这是也可以通过朴素民俗算法实现的界限。对于较大的最大度Δ，我们的算法因此是对先前技术状态的指数改进。
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(logn)-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(log5logn) 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Δ + log6logn) rounds. As a function of n alone, the best previous algorithm therefore had a round complexity of O(logn), which is a bound that can also be achieved by a na'ive folklore algorithm. For large maximum degree Δ, our algorithm hence is an exponential improvement over the previous state of the art.
局部模型中随机复杂性和确定性复杂性之间的指数分离
影响因子：
1.6
作者：
Chang, Yi-Jun;Kopelowitz, Tsvi;Pettie, Seth
通讯作者：
Pettie, Seth