|
|||||
|
|
A note on the online First-Fit algorithm for coloring k-inductive graphs |
|
| Authors: | Shakhar Smorodinsky |
| Affiliation: | Department of Mathematics, Ben-Gurion University, Be'er Sheva 84105, Israel |
| Abstract: | In a FOCS 1990 paper, S. Irani proved that the First-Fit online algorithm for coloring a graph uses at most O(klogn) colors for k-inductive graphs. In this note we provide a very short proof of this fact. |
| Keywords: | On-line algorithms Analysis of algorithms Graph algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |