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. In Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC 2008), volume 2368 of Lecture Notes in Computer Science, pages 89-99. Springer-Verlag, 2008.

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.

Copyright:

This paper is © Springer-Verlag.

Availability:

Available as pdf (223 KB).
Also available at SprinterLink.

Related Papers:

• Comparing first-fit and next-fit for online edge coloring (Journal Paper)