A fast distributed algorithm for (Δ + 1)-edge-coloring
A fast distributed algorithm for (Δ + 1)-edge-coloring
复制标题
一种快速分布式 (Îâ´ – 1)-边缘着色算法
DOI：
10.1016/j.jctb.2021.10.004
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Bernshteyn, Anton
中科院分区：
文献类型：
--
作者：
Bernshteyn, Anton
本文提出了一个确定性的分布式算法，在多项式（Δ，log n）轮中找到一个最大度为Δ的n-顶点图的（Δ +1）-边染色。这是第一个非平凡的分布式边着色算法，只使用Δ+ 1种颜色（匹配Vizing定理给出的边界）。我们的方法受到Grebík和Pikhurko最近证明Vizing定理的可测量版本的启发。
We present a deterministic distributed algorithm in the LOCAL model that finds a proper (Δ+ 1)-edge-coloring of an n-vertex graph of maximum degree Δ in poly (Δ, log n) rounds. This is the first nontrivial distributed edge-coloring algorithm that uses only Δ+ 1 colors (matching the bound given by Vizing's theorem). Our approach is inspired by the recent proof of the measurable version of Vizing's theorem due to Grebík and Pikhurko.
登录
查看更多内容
小调色板分布式边缘着色的复杂性
DOI：
10.1137/1.9781611975031.168
发表时间：
2018
期刊：
SODA 2018
影响因子：
--
作者：
Chang, Yi-Jun;He, Qizheng;Li, Wenzheng;Pettie, Seth;Uitto, Jara
通讯作者：
Uitto, Jara
稀疏图中的并行对称性破缺
DOI：
--
发表时间：
1987
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Andrew V. Goldberg;Serge A. Plotkin;Gregory E. Shannon
通讯作者：
Gregory E. Shannon
DOI：
--
发表时间：
2019
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Hsin;H. Vu
通讯作者：
H. Vu
通过超图最大匹配确定性分布式边缘着色
DOI：
10.1109/focs.2017.25
发表时间：
2017
期刊：
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Manuela Fischer;M. Ghaffari;F. Kuhn
通讯作者：
F. Kuhn
多对数时间确定性网络分解和分布式去随机化
DOI：
--
发表时间：
2019
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Václav Rozhoň;M. Ghaffari
通讯作者：
M. Ghaffari