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 language | English |
---|---|
Title of host publication | Algorithms and Computation |
Editors | Seok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga |
Number of pages | 11 |
Volume | 5369 |
Publisher | Springer |
Publication date | 2009 |
Pages | 89-99 |
ISBN (Print) | 978-3-540-92181-3 |
Publication status | Published - 2009 |
Event | International Symposium on Algorithms and Computation - Surfers Paradise, Australia Duration: 15. Dec 2008 → 17. Dec 2008 Conference number: 19 |
Conference
Conference | International Symposium on Algorithms and Computation |
---|---|
Number | 19 |
Country/Territory | Australia |
City | Surfers Paradise |
Period | 15/12/2008 → 17/12/2008 |