Near-Optimal, Distributed Edge Colouring via the Nibble Method

Devdatt Dubhashi
David A. Grable
Alessandro Panconesi

May 1996

Abstract:

We give a distributed randomized algorithm to edge colour a network. Let G be a graph with n nodes and maximum degree tex2html_wrap_inline28 . Here we prove:

  • If tex2html_wrap_inline30 for some tex2html_wrap_inline32 and tex2html_wrap_inline34 is fixed, the algorithm almost always colours G with tex2html_wrap_inline38 colours in time tex2html_wrap_inline40 .
  • If s > 0 is fixed, there exists a positive constant k such that if tex2html_wrap_inline46 , the algorithm almost always colours G with tex2html_wrap_inline50 colours in time tex2html_wrap_inline52 .
By ``almost always'' we mean that the algorithm may fail, but the failure probability can be made arbitrarily close to 0.

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 PostScript, PDF, DVI.

 
Last modified: 2003-06-08 by webmaster.