an experimental study of a simple, distributed edge coloring algorithm
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. The test cases were chosen based on two objectives  (i) to provide insights into the worst case behavior (in terms of time and quality) of the algorithm and (ii) to test the performance of the algorithm with instances that are likely to arise in practice. Our main results include the following: The empirical results obtained compare very well with the recent empirical results reported by other researchers [5, 6, 18]. The empirical confirm the bounds on the running time and the solution quality as claimed in the theoretical paper. Our results show that for certain classes of graphs the algorithm is likely to perform much better than the analysis suggests The results demonstrate that the algorithm might be well suited (from a theoretical as well as practical stand-point) for edge coloring graphs quickly and efficiently in a distributed setting. Based on our empirical study, we propose a simple modification of the original algorithm with substantially improved performance in practice.
experimentation distributed color algorithm analysis randomization randomized algorithm graph probabilistic analysis optimality test families case object behavior timing quality performance practical research paper class demonstrate empirical studies point random graph