论文标题
快速着色而不学习邻居的颜色
Coloring Fast Without Learning Your Neighbors' Colors
论文作者
论文摘要
我们给出了距离的改进的随机杂货算法 - $ 2 $颜色，使用$δ^2+1 $颜色，并以$ O（\ log n）$ rounds运行，改善了最近的$ o（\ logδ\ cdot \ log n）$ - 在[Halldórsson，kuhn，kuhn，Maus，Maus; PODC '20]。然后，我们将时间复杂度提高到$ o（\logδ） + 2^{o（\ sqrt {\ log \ log \ log n}）} $。
We give an improved randomized CONGEST algorithm for distance-$2$ coloring that uses $Δ^2+1$ colors and runs in $O(\log n)$ rounds, improving the recent $O(\log Δ\cdot \log n)$-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to $O(\log Δ) + 2^{O(\sqrt{\log\log n})}$.
