论文标题
$δ$的分布式边缘着色polygarithmic
Distributed Edge Coloring in Time Polylogarithmic in $Δ$
论文作者
论文摘要
我们为边缘着色问题提供了新的确定性算法，这是经典且经过深入研究的分布式局部对称性破坏问题之一。作为我们的主要结果，我们表明可以在本地模型中计算出$（2δ-1）$ - 边缘着色。这改善了Balliu，Kuhn和Olivetti [PODC '20]的结果，后者给出了对$δ$的准二旋律依赖性的算法。我们进一步表明，在拥挤模型中，可以在$ \ mathrm {poly} \logΔ+ o（\ log^* n）$ rounds中计算出$（8+ \ varepsilon）δ$ - edge着色。可以在Escest模型中实现的最佳以前的$ O（δ）$ - 边缘着色算法是Barenboim和Elkin [PODC '11]，它计算了$ 2^{o（1/\ varepsilon）}Δ$ - 在时间$ o（Δ^^^^^^\ VAREPSILON + log \ log^n）中， $ \ varepsilon \ in（0,1] $。
We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main result, we show that a $(2Δ-1)$-edge coloring can be computed in time $\mathrm{poly}\logΔ+ O(\log^* n)$ in the LOCAL model. This improves a result of Balliu, Kuhn, and Olivetti [PODC '20], who gave an algorithm with a quasi-polylogarithmic dependency on $Δ$. We further show that in the CONGEST model, an $(8+\varepsilon)Δ$-edge coloring can be computed in $\mathrm{poly}\logΔ+ O(\log^* n)$ rounds. The best previous $O(Δ)$-edge coloring algorithm that can be implemented in the CONGEST model is by Barenboim and Elkin [PODC '11] and it computes a $2^{O(1/\varepsilon)}Δ$-edge coloring in time $O(Δ^\varepsilon + \log^* n)$ for any $\varepsilon\in(0,1]$.
