𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fast Distributed Algorithms for Brooks–Vizing Colorings

✍ Scribed by David A Grable; Alessandro Panconesi


Book ID
102573639
Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
208 KB
Volume
37
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis


Let G be a ⌬-regular graph with n vertices and girth at least 4 such that ⌬ 4 log n. We give very simple, randomized, distributed algorithms for vertex Ž . coloring G with ⌬rk colors in O k q log n communication rounds, where k s Ž . O log ⌬ . The algorithm may fail or exceed the above running time, but the Ž . probability that this happens is o 1 , a quantity that goes to zero as n grows. The probabilistic analysis relies on a powerful generalization of Azuma's martingale inequality that we dub the Method of Bounded Variances.


📜 SIMILAR VOLUMES


A fast algorithm for equitable coloring
✍ Henry A. Kierstead; Alexandr V. Kostochka; Marcelo Mydlarz; Endre Szemerédi 📂 Article 📅 2010 🏛 Springer-Verlag 🌐 English ⚖ 399 KB