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: 2008-08-26 by Lene Monrad Favrholdt <lenem@imada.sdu.dk>