Nearly optimal distributed edge colouring in O(log log n) rounds
David A. Grable, Alessandro Panconesi · 1997
An extremely simple distributed randomized algorithm is presented which with high probability properly edge colours a given graph using (1+ ")\\Delta colours, where \\Delta is the maximum degree of the graph and " is any given positive constant. The algorithm is very fast. In particular, for graphs with sufficiently large vertex degrees (larger than polylog n, but smaller than any positive power of n), the algorithm requires only O(log log n) communication rounds. The algorithm is inherently distributed, but can be implemented on the PRAM, where it requires O(m\\Delta) processors and O(log \\Delta log log n) time, or in a sequential setting, where it requires O(m\\Delta) time. 1 Introduction The edge colouring problem is a much studied problem in the theory of algorithms, graph theory, and combinatorics, whose relevance to computer science stems from its applications to scheduling and resource allocation problems [6, 11, 14, 17, 19, 12, 24, among others]. Given an input graph, the problem ...