Near-Optimal, Distributed Edge Colouring via the Nibble Method

Forfattere

  • Devdatt P. Dubhashi
  • David A. Grable
  • Alessandro Panconesi

DOI:

https://doi.org/10.7146/brics.v3i11.19974

Resumé

We give a distributed randomized algorithm to edge colour a network. Let G be a graph
with 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 always
colours 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 time
O(logn + log^s n log log n).
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¨odl. The analysis makes use of a powerful large deviation inequality for functions
of independent random variables.

Downloads

Publiceret

1996-01-11

Citation/Eksport

Dubhashi, D. P., Grable, D. A., & Panconesi, A. (1996). Near-Optimal, Distributed Edge Colouring via the Nibble Method. BRICS Report Series, 3(11). https://doi.org/10.7146/brics.v3i11.19974