(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science

   
On-Line Edge Coloring with a Fixed Number of Colors
Lene M. Favrholdt, Morten N. Nielsen
Algorithmica 35(2): 176-191, 2003

We investigate a variant of on-line edge-coloring in which there is a fixed number of colors available and the aim is to color as many edges as possible. We prove upper and lower bounds on the performance of different classes of algorithms for the problem. Furthermore, we determine the performance of two specific algorithms, First-Fit and Next-Fit.

The publication is available at www.springerlink.com (subscription may be required).