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

Nummer

Nr. 11 (1996): RS-11 Near-Optimal, Distributed Edge Colouring via the Nibble Method

Sektion

Artikler

Licens

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).