论文标题
本地词汇$（δ+1）$ - sublinear（$δ$）的着色
Locally-iterative $(Δ+1)$-Coloring in Sublinear (in $Δ$) Rounds
论文作者
论文摘要
分布式图着色是分布式计算中最广泛研究的问题之一。有一个典型的分布式图形着色算法被称为本地素质着色算法，首先是在[szegedy and vishwanathan，stoc'93]的开创性作品中正式化的。在这样的算法中，每个顶点迭代都根据当前邻居的当前着色的预定功能更新自己的颜色。由于其框架的简单性和自然性，在理论和实践中，本地著作的着色算法都具有重要意义。在本文中，我们给出了$ o（δ^{3/4} \logδ）+\ log^*n $运行时间的本地词（δ+1）$ - 着色算法。这是第一个本地词（δ+1）$ - 颜色算法，带有sublinear-in- $δ$运行时间，回答了最近突破中提出的主要开放问题[Barenboim，Elkin和Goldberg，Jacm'21]。我们算法的关键组成部分是本地词法过程，它将$ O（δ^2）$ - 颜色转换为$（δ+o（δ+o（δ^{3/4} \logΔ））$ - 以$ O（δ）$时间的颜色。在此过程中，我们处理编码（ARB）有缺陷色素的特殊正确着色，并以当地术语方式二次减少使用的颜色数量。作为我们结果的主要应用，我们还为$（δ+1）$ - 颜色（δ^{3/4} \logδ）+\ log^*n $稳定时间提供了一种自动稳定的分布式算法。据我们所知，这是第一个以$（δ+1）$的自动稳定算法 - 与sublinear-in- $δ$稳定时间的颜色。
Distributed graph coloring is one of the most extensively studied problems in distributed computing. There is a canonical family of distributed graph coloring algorithms known as the locally-iterative coloring algorithms, first formalized in the seminal work of [Szegedy and Vishwanathan, STOC'93]. In such algorithms, every vertex iteratively updates its own color according to a predetermined function of the current coloring of its local neighborhood. Due to the simplicity and naturalness of its framework, locally-iterative coloring algorithms are of great significance both in theory and practice. In this paper, we give a locally-iterative $(Δ+1)$-coloring algorithm with $O(Δ^{3/4}\logΔ)+\log^*n$ running time. This is the first locally-iterative $(Δ+1)$-coloring algorithm with sublinear-in-$Δ$ running time, and answers the main open question raised in a recent breakthrough [Barenboim, Elkin, and Goldberg, JACM'21]. A key component of our algorithm is a locally-iterative procedure that transforms an $O(Δ^2)$-coloring to a $(Δ+O(Δ^{3/4}\logΔ))$-coloring in $o(Δ)$ time. Inside this procedure we work on special proper colorings that encode (arb)defective colorings, and reduce the number of used colors quadratically in a locally-iterative fashion. As a main application of our result, we also give a self-stabilizing distributed algorithm for $(Δ+1)$-coloring with $O(Δ^{3/4}\logΔ)+\log^*n$ stabilization time. To the best of our knowledge, this is the first self-stabilizing algorithm for $(Δ+1)$-coloring with sublinear-in-$Δ$ stabilization time.
