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

Alessandro Panconesi
Institut für Informatik
Freie Universität Berlin
Takustr. 9
14195 Berlin, Germany

Report B 96-06
July 1996

Get the report here or by anonymous ftp: 
File:   pub/reports/
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.