Comparing First-Fit and Next-Fit for Online Edge Coloring

Martin R. Ehmsen, Lene Monrad Favrholdt, Jens Svalgaard Kohrt, Rodica Mihai

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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.
Original languageEnglish
Title of host publicationAlgorithms and Computation
EditorsSeok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga
Number of pages11
Volume5369
PublisherSpringer
Publication date2009
Pages89-99
ISBN (Print)978-3-540-92181-3
Publication statusPublished - 2009
EventInternational Symposium on Algorithms and Computation - Surfers Paradise, Australia
Duration: 15. Dec 200817. Dec 2008
Conference number: 19

Conference

ConferenceInternational Symposium on Algorithms and Computation
Number19
Country/TerritoryAustralia
CitySurfers Paradise
Period15/12/200817/12/2008

Fingerprint

Dive into the research topics of 'Comparing First-Fit and Next-Fit for Online Edge Coloring'. Together they form a unique fingerprint.

Cite this