A note on the online first-fit algorithm for coloring k-inductive graphs Academic Article uri icon


  • Page 1. Information Processing Letters 109 (2008) 44–45 Contents lists available at ScienceDirect Information Processing Letters www.elsevier.com/locate/ipl A note on the online First-Fit algorithm for coloring k-inductive graphs Shakhar Smorodinsky Department of Mathematics, Ben-Gurion University, Be'er Sheva 84105, Israel article info abstract Article history: Received 19 February 2008 Received in revised form 29 July 2008 Available online 23 August 2008 Communicated by K. Iwama Keywords: On-line algorithms Analysis of algorithms Graph algorithms In a FOCS 1990 paper, S. Irani proved that the First-Fit online algorithm for coloring a graph uses at most O(k logn) colors for k-inductive graphs. In this note we provide a very short proof of this fact. © 2008 Elsevier BV All rights reserved. 1. Introduction …

publication date

  • January 1, 2008