TY - JOUR
AU - Dubhashi, Devdatt P.
AU - Grable, David A.
AU - Panconesi, Alessandro
PY - 1996/01/11
Y2 - 2024/05/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
SP -
AB - We give a distributed randomized algorithm to edge colour a network. Let G be a graph<br />with n nodes and maximum degree Delta. Here we prove:<br /> If Delta = Omega(log^(1+delta) n) for some delta > 0 and lambda > 0 is fixed, the algorithm almost always<br />colours G with (1 + lambda)Delta colours in time O(log n).<br /> 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 time<br />O(logn + log^s n log log n).<br />By "almost always" we mean that the algorithm may fail, but the failure probability can be<br />made arbitrarily close to 0.<br />The algorithm is based on the nibble method, a probabilistic strategy introduced by<br />Vojtech RÂ¨odl. The analysis makes use of a powerful large deviation inequality for functions<br />of independent random variables.
ER -