๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Nearly optimal distributed edge coloring in O(log log n) rounds

โœ Scribed by David A. Grable; Alessandro Panconesi

Book ID
101270649
Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
220 KB
Volume
10
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

โœฆ Synopsis

An extremely simple distributed randomized algorithm is presented which with

ลฝ

. high probability properly edge colors a given graph using 1 q โŒฌ 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.

๐Ÿ“œ SIMILAR VOLUMES

Perfect Information Leader Election in l
Perfect Information Leader Election in log* n+O(1) Rounds
โœ Alexander Russell; David Zuckerman ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 168 KB

In the leader election problem, n players wish to elect a random leader. The difficulty is that some coalition of players may conspire to elect one of its own members. We adopt the perfect information model: all communication is by broadcast, and the bad players have unlimited computational power. P