(Logo)   IMADA
University of Southern Denmark 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.