Towards the locality of Vizing’s theorem
Towards the locality of Vizing’s theorem
复制标题
维辛定理的局部性
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
H. Vu
中科院分区：
文献类型：
--
作者：
Hsin;H. Vu
Vizing 表明，使用 Δ + 1 种颜色就足以为简单图的边缘着色，其中 Δ 是图的最大阶数。然而，到目前为止，还没有有效的分布式边缘着色算法来获得这种着色，即使对于常度图也是如此。当前最接近此颜色数量的算法是 Chang 等人在 (n) 轮中运行的随机 (Δ + θ(√Δ)) 边缘着色算法。 [SODA 2018] 以及 Ghaffari 等人在 (Δ, logn) 轮中运行的确定性 (Δ + (n)) 边缘着色算法。 [STOC 2018].我们提出了两种以 (Δ,logn) 轮运行的分布式边缘着色算法。第一个算法采用随机化，仅使用 Δ+2 种颜色。第二种算法是使用 Δ+ O(logn/ loglogn) 颜色的确定性算法。我们的方法是将分布式边缘着色问题简化为在线和受限版本的球入垃圾箱问题。如果 ℓ 是箱的最大负载，我们的算法使用 Δ + 2ℓ − 1 种颜色。我们展示了如何在随机化的情况下实现 ℓ = 1 和在没有随机化的情况下实现 ℓ = O(logn / loglogn)。
Vizing showed that it suffices to color the edges of a simple graph using Δ + 1 colors, where Δ is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithm is known for obtaining such coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized (Δ + Θ(√Δ))-edge-coloring algorithm that runs in (n) rounds by Chang et al. [SODA 2018] and the deterministic (Δ + (n))-edge-coloring algorithm that runs in (Δ, logn) rounds by Ghaffari et al. [STOC 2018]. We present two distributed edge-coloring algorithms that run in (Δ,logn) rounds. The first algorithm, with randomization, uses only Δ+2 colors. The second algorithm is a deterministic algorithm that uses Δ+ O(logn/ loglogn) colors. Our approach is to reduce the distributed edge-coloring problem into an online and restricted version of balls-into-bins problem. If ℓ is the maximum load of the bins, our algorithm uses Δ + 2ℓ − 1 colors. We show how to achieve ℓ = 1 with randomization and ℓ = O(logn / loglogn) without randomization.
影响因子：
1.3
作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
通讯作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
小调色板分布式边缘着色的复杂性
DOI：
10.1137/1.9781611975031.168
发表时间：
2018
期刊：
SODA 2018
影响因子：
--
作者：
Chang, Yi-Jun;He, Qizheng;Li, Wenzheng;Pettie, Seth;Uitto, Jara
通讯作者：
Uitto, Jara