@article{Dubhashi_Grable_Panconesi_1996, title={Near-Optimal, Distributed Edge Colouring via the Nibble Method}, volume={3}, url={https://tidsskrift.dk/brics/article/view/19974}, DOI={10.7146/brics.v3i11.19974}, abstractNote={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.}, number={11}, journal={BRICS Report Series}, author={Dubhashi, Devdatt P. and Grable, David A. and Panconesi, Alessandro}, year={1996}, month={Jan.} }