首页|A fast distributed algorithm for (Delta+1)-edge-coloring
A fast distributed algorithm for (Delta+1)-edge-coloring
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
We present a deterministic distributed algorithm in the LOCAL model that finds a proper (Delta + 1)-edge-coloring of an n-vertex graph of maximum degree Delta in poly(Delta, log n) rounds. This is the first nontrivial distributed edge-coloring algorithm that uses only Delta + 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 Grebik and Pikhurko. (c) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier
