## 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 |

## Fingerprint

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