论文标题
克服分布式着色的拥塞
Overcoming Congestion in Distributed Coloring
论文作者
论文摘要
我们提出了一种新技术，可以有效地采样和传达分布式抽样空间的大量元素。当在最近的本地算法的上下文中使用$（\ operatorName {gegar} +1）$ - 列表颜色（D1LC）时，这使我们可以在$ o（\ log^5 \ log n）$ colest $ colests中求解D1LC，并且仅在$ o（\ log log^* n）$ founds $ $ $ $ $ $上（ 该技术还可以立即应用在本地测试某些图形属性，并估算$ O（1）$ o（1）$ coless Rounds，W.H.P.的本地子图的稀疏/密度。
We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent LOCAL algorithm for $(\operatorname{degree}+1)$-list-coloring (D1LC), this allows us to solve D1LC in $O(\log^5 \log n)$ CONGEST rounds, and in only $O(\log^* n)$ rounds when the graph has minimum degree $Ω(\log^7 n)$, w.h.p. The technique also has immediate applications in testing some graph properties locally, and for estimating the sparsity/density of local subgraphs in $O(1)$ CONGEST rounds, w.h.p.
