Near-Optimal, Distributed Edge Colouring via the Nibble Method
Devdatt Dubhashi May 1996 |

## Abstract:We give a distributed randomized algorithm to edge colour a
network. Let - If for
some and is fixed, the algorithm almost always
colours
*G*with colours in time . - If
*s*> 0 is fixed, there exists a positive constant*k*such that if , the algorithm almost always colours*G*with colours in time .
The algorithm is based on the nibble method, a probabilistic strategy introduced by Vojtech Rödl. The analysis makes use of a powerful large deviation inequality for functions of independent random variables.
Available as |

Last modified: 2003-06-08 by webmaster.