The Complexity of Distributed Edge Coloring with Small Palettes
The Complexity of Distributed Edge Coloring with Small Palettes
复制标题
小调色板分布式边缘着色的复杂性
DOI：
10.1137/1.9781611975031.168
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Uitto, Jara
中科院分区：
文献类型：
--
作者：
Chang, Yi-Jun;He, Qizheng;Li, Wenzheng;Pettie, Seth;Uitto, Jara
分布式边缘着色的复杂性在很大程度上取决于作为最大度数Δ函数的调色板大小。在本文中，我们探讨了不同调色板大小的情况下，局部模型中边缘着色的复杂性。我们的结果如下：我们简化了Brandt等人的声音消除技术。[9]证明了(2Δ-2)-边染色所需的Ω(LogΔLogn)时间W.H.P.和Ω(LOGΔn)时间是确定性的，即使在树上也是如此。该简化技术基于两个概念：不规则运行时间的概念(网络组件在规定的但不规律的时间终止算法)和将弱下界转换为强界的一般观察结果。我们给出了一种随机边着色算法，它可以使用小到的调色板大小，这是随机化方法的自然障碍。该算法的运行时间为Mosto(LOGΔ·TLLL)，其中TLLL是构造Lovász局部引理的允许版本的复杂性，提出了一种新的树结构依赖图的分布式Lovász局部引理算法，由此得到了一种运行时间为(LOG LOGN)时间的树的(1+∊)Δ)边着色算法.该算法源于两个新的结果：树形结构实例的确定性O(Logn)时间LLL算法和将依赖图分解成独立的O(Logn)大小的LLL实例的随机化O(Logn)时间图破碎法。计算(Δ+1)边着色的一个自然方法(维辛定理)是通过迭代地对图的部分重新着色来扩展部分着色，例如，通过“增加路径”。我们证明了这种方法可能是可行的，但在最坏的情况下需要对直径为Ω(Δ的子图进行重新着色)。这与布鲁克斯定理的分布式算法[32]形成了鲜明的对比，后者利用了(LogΔn)长度增长路径的存在。
The complexity of distributed edge coloring depends heavily on thepalette sizeas a function of the maximum degree Δ. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows.We simplify theround eliminationtechnique of Brandt et al. [9] and prove that (2Δ – 2)-edge coloring requires Ω(logΔlogn) time w.h.p. and Ω(logΔn) time deterministically,even on trees. The simplified technique is based on two ideas: the notion of anirregular running time(in which network components terminate the algorithm at prescribed, but irregular times) and some general observations that transformweaklower bounds intostrongerones.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 the algorithm is at mostO(log Δ ·TLLL), whereTLLLis the complexity of a permissive version of the constructive Lovász local lemma.We develop a new distributed Lovász local lemma algorithm fortree-structured dependency graphs, which leads to a (1 +∊)Δ-edge coloring algorithm for trees running inO(log logn) time. This algorithm arises from two new results: a deterministicO(logn)-time LLL algorithm for tree-structured instances, and a randomizedO(log logn)-timegraph shatteringmethod for breaking the dependency graph into independentO(logn)-size LLL instances.A natural approach to computing (Δ + 1)-edge colorings (Vizing's theorem) is to extend partial colorings by iteratively re-coloring parts of the graph, e.g., via “augmenting paths.” We prove that this approach may be viable, but in the worst case requires recoloring subgraphs of diameter Ω(Δ logn). This stands in contrast to distributed algorithms for Brooks’ theorem [32], which exploit the existence ofO(logΔn)-length augmenting paths.
登录
查看更多内容
影响因子：
1.3
作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
通讯作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
一种用 Δ + 1 种颜色为图的边缘着色的高效算法
DOI：
--
发表时间：
1982
期刊：
影响因子：
--
作者：
E. Arjomandi
通讯作者：
E. Arjomandi
局部模型中随机复杂性和确定性复杂性之间的指数分离
影响因子：
1.6
作者：
Chang, Yi-Jun;Kopelowitz, Tsvi;Pettie, Seth
通讯作者：
Pettie, Seth
DOI：
--
发表时间：
1983
期刊：
--
影响因子：
--
作者：
通讯作者：
--
DOI：
--
发表时间：
1998
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
David A. Grable
通讯作者：
David A. Grable