Nearly optimal distributed edge colouring in $O(\log \log n)$ rounds
David A. Grable
Institut für Informatik
Humboldt-Universität zu Berlin
Unter den Linden 6
10099 Berlin, Germany
grable@informatik.hu-berlin.de
Alessandro Panconesi
Institut für Informatik
Freie Universität Berlin
Takustr. 9
14195 Berlin, Germany
ale@inf.fu-berlin.de
Report B 96-06
July 1996
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-96-06.ps.gz
Nearly optimal distributed edge \\colouring in $O(\log \log n)$ rounds
An extremely simple distributed randomized edge colouring algorithm is
given which, for any positive constants $\varepsilon$ and $c$ and a
graph $G$ with minimum degree $\Omega(n^{c/\log \log n})$, produces with
high probability a proper edge colouring of $G$ using
$(1+\varepsilon)\Delta(G)$ colours in only $O(\log \log n)$ communication
rounds.