A Tight Analysis of Kierstead-Trotter Algorithm for Online Unit Interval Coloring

Tetsuya ARAKI  Koji M. KOBAYASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.10   pp.1885-1887
Publication Date: 2016/10/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1885
Type of Manuscript: LETTER
Category: Algorithms and Data Structures
interval coloring,  unit interval,  online problem,  interval graph,  

Full Text: PDF(75.6KB)>>
Buy this Article

The online interval coloring problem has been extensively studied for many years. Kierstead and Trotter (Congressus Numerantium 33, 1981) proved that their algorithm is an optimal online algorithm for this problem. The number of colors used by the algorithm is at most 3ω(G)-2, where ω(G) is the size of the maximum clique in a given graph G. Also, they presented an instance for which the number of colors used by any online algorithm is at least 3ω(G)-2. This instance includes intervals with various lengths, which cannot be applied to the case when the lengths of the given intervals are restricted to one, i.e., the online unit interval coloring problem. In this case, the current best upper and lower bounds on the number of colors used by an online algorithm are 2ω(G)-1 and 3ω(G)/2 respectively by Epstein and Levy (ICALP2005). In this letter, we conduct a complete performance analysis of the Kierstead-Trotter algorithm for online unit interval coloring, and prove it is NOT optimal. Specifically, we provide an upper bound of 3ω(G)-3 on the number of colors used by their algorithm. Moreover, the bound is the best possible.