# Comparing first-fit and next-fit for online edge coloring

- Description:
- Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, and Rodica Mihai.
*Comparing first-fit and next-fit for online edge coloring*.*Theoretical Computer Science*, 411:1734-1741, 2010. - Abstract:
- We study the performance of the algorithms First-Fit and Next-Fit for two online edge coloring problems. In the min-coloring problem, all edges must be colored using as few colors as possible. In the max-coloring problem, a fixed number of colors is given, and as many edges as possible should be colored. Previous analysis using the competitive ratio has not separated the performance of First-Fit and Next-Fit, but intuition suggests that First-Fit should be better than Next-Fit. We compare First-Fit and Next-Fit using the relative worst-order ratio, and show that First-Fit is better than Next-Fit for the min-coloring problem. For the max-coloring problem, we show that First-Fit and Next-Fit are not strictly comparable, i.e., there are graphs for which First-Fit is better than Next-Fit and graphs where Next-Fit is slightly better than First-Fit.
- Availability:
- Available as pdf (330 KB).

Also available at ScienceDirect. - Related Papers:
- Comparing first-fit and next-fit for online edge coloring (Conference Paper)

See also other papers by Jens Svalgaard Kohrt.