שחר סמורודינסקי
אקדמי בכיר
A note on the online First-Fit algorithm for coloring k-inductive graphs
In a FOCS 1990 paper, S. Irani proved that the First-Fit online algorithm for coloring a graph uses at most O (k log n) colors for k-inductive graphs. In this note we provide a very short proof of this fact.
| שפת פרסום | אנגלית |
| דפים | 44-45 |
| כתב עת | Information Processing Letters |
| כרך | 109 |
| נושא מספר | 1 |
| סטטוס פרסום | פורסם - 16.12.2008 |
Keywords
Analysis of algorithms
Graph algorithms
On-line algorithms
ASJC Scopus subject areas
Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications
