IMADA - Department of Mathematics and Computer Science |

**Comparing First-Fit and Next-Fit for Online Edge Coloring***Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, and Rodica Mihai*- 19th International Symposium on Algorithms and Computation, to appear
We study the performance of the two well-known edge coloring algorithms First-Fit and Next-Fit using the relative worst-order ratio. Previous analysis using the competitive ratio have not been able to separate their performance. We first consider the min-coloring problem and conclude that First-Fit is better than Next-Fit. Next, we consider the max-coloring problem, and conclude, surprisingly, that First-Fit and Next-Fit are not comparable. |

IMADA HOME | SDU HOME | Previous page Last modified: 2017-06-10 by Lene Monrad Favrholdt <lenem@imada.sdu.dk> |