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

Originalsprog | Engelsk |
---|---|

Titel | Algorithms and Computation |

Redaktører | Seok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga |

Antal sider | 11 |

Vol/bind | 5369 |

Forlag | Springer |

Publikationsdato | 2009 |

Sider | 89-99 |

ISBN (Trykt) | 978-3-540-92181-3 |

Status | Udgivet - 2009 |

Begivenhed | International Symposium on Algorithms and Computation - Surfers Paradise, Australien Varighed: 15. dec. 2008 → 17. dec. 2008 Konferencens nummer: 19 |

### Konference

Konference | International Symposium on Algorithms and Computation |
---|---|

Nummer | 19 |

Land/Område | Australien |

By | Surfers Paradise |

Periode | 15/12/2008 → 17/12/2008 |

## Fingeraftryk

Dyk ned i forskningsemnerne om '**Comparing First-Fit and Next-Fit for Online Edge Coloring**'. Sammen danner de et unikt fingeraftryk.