An experimental study of a simple, distributed edge coloring algorithm
MADHAV V. MARATHE, Alessandro Panconesi, L. Dean Risinger · 2000
We conduct an experimental analysis of a distributed, randomized algorithm for edge coloring simple undirected graphs. The algorithm is extremely simple, yet, according to the probabilistic analysis, it computes nearly optimal colorings very quickly [12]. We test the algorithm on a number of random as well as non-random graph families.