论文标题
时间时代的分布式边缘着色
Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
论文作者
论文摘要
在分布式图算法领域中，以$2δ-1 $颜色为$2δ-1 $颜色的$ n $ node图$δ$的边缘的边缘是最大程度$δ$的边缘的问题之一。尽管在理解这个问题方面取得了很大的进步，但运行时间对$δ$的依赖性是一个长期以来的开放问题。最近，Kuhn [Soda '20]表明，该问题可以在时间$ 2^{o（\ sqrt {\logΔ}）}}+o（\ log log^* n）$中解决。 在本文中，我们研究了分布式本地模型中的边缘着色问题。我们表明，$（\ Mathit {度} +1）$ - 列表边缘着色问题，因此也可以在时间$ \ log^{o（\ log \logΔ）}δ+ o（\ log log^* n）$中确定地解决$（2Δ-1）$ - 边缘着色问题。这比Kuhn [Soda '20]的结果有了重大改进。
The problem of coloring the edges of an $n$-node graph of maximum degree $Δ$ with $2Δ- 1$ colors is one of the key symmetry breaking problems in the area of distributed graph algorithms. While there has been a lot of progress towards the understanding of this problem, the dependency of the running time on $Δ$ has been a long-standing open question. Very recently, Kuhn [SODA '20] showed that the problem can be solved in time $2^{O(\sqrt{\logΔ})}+O(\log^* n)$. In this paper, we study the edge coloring problem in the distributed LOCAL model. We show that the $(\mathit{degree}+1)$-list edge coloring problem, and thus also the $(2Δ-1)$-edge coloring problem, can be solved deterministically in time $\log^{O(\log\logΔ)}Δ+ O(\log^* n)$. This is a significant improvement over the result of Kuhn [SODA '20].
