TY - JOUR
AU - Devdatt Dubhashi
AU - David Grable
AU - Alessandro Panconesi
PY - 1996/01/11
Y2 - 2019/10/20
TI - Near-Optimal, Distributed Edge Colouring via the Nibble Method
JF - BRICS Report Series
JA - BRICS
VL - 3
IS - 11
SE - Articles
DO - 10.7146/brics.v3i11.19974
UR - https://tidsskrift.dk/brics/article/view/19974
AB - We give a distributed randomized algorithm to edge colour a network. Let G be a graphwith n nodes and maximum degree Delta. Here we prove: If Delta = Omega(log^(1+delta) n) for some delta > 0 and lambda > 0 is fixed, the algorithm almost alwayscolours G with (1 + lambda)Delta colours in time O(log n). If s > 0 is fixed, there exists a positive constant k such that if Delta = omega(log^k n), the algorithm almost always colours G with Delta + Delta / log^s n = (1+o(1))Delta colours in timeO(logn + log^s n log log n).By "almost always" we mean that the algorithm may fail, but the failure probability can bemade arbitrarily close to 0.The algorithm is based on the nibble method, a probabilistic strategy introduced byVojtech RÂ¨odl. The analysis makes use of a powerful large deviation inequality for functionsof independent random variables.
ER -