论文标题
使用应用程序快速分布式顶点分裂
Fast Distributed Vertex Splitting with Applications
论文作者
论文摘要
我们提出$ {\ rm poly \ log \ log n} $ - 圆形随机分布式算法来计算顶点分组，这是图形的顶点的划分为$ k $零件，以使得$ d $ d（u）$的节点在每个部分中具有$ \ \ \ \ \ \ \ d $ d（u）$的节点。我们的技术可以看作是朝着$ {\ rm poly \ log \ log n} $ - lovász局部引理的圆形算法的第一个进度。 作为我们结果的主要应用，我们获得了一个随机的$ {\ rm poly \ log \ log \ log n} $ - $（1+ε）δ$ - gede $ n $ n $ n $ n $ node图的圆形拥塞算法，用于任何$ε> 0 $。此外，我们的结果改善了有缺陷的着色和某些紧密列表着色问题的计算。 所有结果即使在本地模型中，所有结果也会呈指数指数级别的复杂性。
We present ${\rm poly\log\log n}$-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into $k$ parts such that a node of degree $d(u)$ has $\approx d(u)/k$ neighbors in each part. Our techniques can be seen as the first progress towards general ${\rm poly\log\log n}$-round algorithms for the Lovász Local Lemma. As the main application of our result, we obtain a randomized ${\rm poly\log\log n}$-round CONGEST algorithm for $(1+ε)Δ$-edge coloring $n$-node graphs of sufficiently large constant maximum degree $Δ$, for any $ε>0$. Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.
