Premium
Nearly optimal distributed edge coloring in O(log log n) rounds
Author(s) -
Grable David A.,
Panconesi Alessandro
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199705)10:3<385::aid-rsa6>3.0.co;2-s
Subject(s) - binary logarithm , combinatorics , log log plot , graph , vertex (graph theory) , edge coloring , mathematics , randomized algorithm , constant (computer programming) , distributed algorithm , discrete mathematics , computer science , graph power , line graph , distributed computing , programming language
An extremely simple distributed randomized algorithm is presented which with high probability properly edge colors a given graph using (1 + ϵ)Δ colors, where Δ 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Δ) processors and O(log Δ log log n) time, or in a sequential setting, where it requires O(mΔ) time. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 385–405 (1997)