Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
复制标题
分布式边缘着色和构造性 Lovász 局部引理的特例
DOI：
10.1145/3365004
复制
发表时间：
2020
影响因子：
1.3
通讯作者：
Uitto, Jara
中科院分区：
文献类型：
--
作者：
Chang, Yi-Jun;He, Qizheng;Li, Wenzheng;Pettie, Seth;Uitto, Jara
分布式边缘着色的复杂性在很大程度上取决于作为最大度数Δ函数的调色板大小。在这篇文章中，我们探讨了在不同调色板大小的情况下，局部模型中边缘着色的复杂性。我们的结果如下：下界：首先，我们简化了Brandt等人的边界消除技术[16]，并证明了(2-Δ−，2)-边染色需要高概率的对数(Ω，Δ)时间和对数(Ω，Δ，n)时间，即使在树上也是如此。其次，我们证明了一种计算(Δ+1)-边着色的自然方法(Visting定理)，即通过迭代重着色子图来扩展任意部分着色，需要Ω(Δlogn)时间。一般图的上界：我们给出了一个随机边着色算法，它可以使用小到Δ+？(√Δ)的调色板大小，这是随机化方法的自然障碍。我们的(1+ε)Δ-边着色算法)的运行时间通常是通过调用分布式Lovász局部引理(ε−)来控制的。例如，使用Chung-Pettie-Su LLL算法，我们计算了当ε)Δ(ε≥(log3Δ)/√Δ)时Ino(Logn)时间，当Δ(1)时(ε=Ω(1)时，oro(Loglogn)+(Loglogn)3+o(1)时间)时的(1+log3-边着色Ino(Logn)时间。当Δ是次对数指数时，性能通过Ghaffari-Harris-Kuhn Lll算法得到改善。树的上界：我们证明了Ω(ΩΔLogn)下界可以在树上几乎匹配。为了建立这一结果，我们为树结构依赖图提出了一种新的分布式Lovász局部引理算法，该算法自然地产生于在树上运行的1轮概率算法。具体地说，我们的树的(1+ε)Δ-边着色算法)当ε))⋅(1/logmax{loglogn\logloglogn，loglogΔlogn})时间为O(ε≥(log3Δ)/√Δ，oro(max{loglogn\logloglogn，logΔlogn}))时ε=Ω(1)。
The complexity of distributed edge coloring depends heavily on thepalette sizeas a function of the maximum degree Δ. In this article, we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows.Lower Bounds:First, we simplify theround eliminationtechnique of Brandt et al. [16] and prove that (2Δ −2)-edge coloring requires Ω (logΔlogn) time with high probability and Ω (logΔn) time deterministically,even on trees. Second, we show that a natural approach to computing (Δ +1)-edge colorings (Vizing’s theorem), namely, extending an arbitrary partial coloring by iteratively recoloring subgraphs, requires Ω (Δ logn) time.Upper Bounds on General Graphs:We give a randomized edge coloring algorithm that can use palette sizes as small as Δ + Õ(√Δ), which is a natural barrier for randomized approaches. The running time of our (1+ε)Δ-edge coloring algorithm is usually dominated byO(\log ε−1) calls to a distributed Lovász local lemma (LLL) algorithm. For example, using the Chung-Pettie-Su LLL algorithm, we compute a (1+ε)Δ-edge coloring inO(logn) time when ε ≥ (log3Δ) / √ Δ , orO(logΔn) + (log logn)3 +o(1)time when ε = Ω (1). When Δ is sublogarithmic innthe performance is improved with the Ghaffari-Harris-Kuhn LLL algorithm.Upper Bounds on Trees:We show that the Ω (logΔlogn) lower bound can be nearly matched on trees. To establish this result, we develop a new distributed Lovász local lemma algorithm fortree-structured dependency graphs, which arise naturally fromO(1)-round probabilistic algorithms run on trees. Specifically, our (1+ε)Δ-edge coloring algorithm for trees takesO(log (1 / ε)) ⋅ max { log logn\ log log logn, loglog Δlogn} time when ε ≥ (log3Δ) / √ Δ, orO(max { log logn\ log log logn, logΔlogn}) time when ε = Ω (1).
登录
查看更多内容
影响因子：
1.3
作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
通讯作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
DOI：
10.1002/rsa.3240020402
发表时间：
1991-12
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
J. Beck
通讯作者：
J. Beck
线性（δ）时间内的分布式（δ+1）着色
DOI：
--
发表时间：
2009
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Leonid Barenboim;Michael Elkin
通讯作者：
Michael Elkin
线性（Delta）时间的分布式（Delta 1）着色
DOI：
--
发表时间：
2008
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Leonid Barenboim;Michael Elkin;F. Kuhn
通讯作者：
F. Kuhn
一种用 Δ + 1 种颜色为图的边缘着色的高效算法
DOI：
--
发表时间：
1982
期刊：
影响因子：
--
作者：
E. Arjomandi
通讯作者：
E. Arjomandi