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

Tetsuya ARAKI; Koji M. KOBAYASHI

doi:10.1587/transfun.E99.A.1885

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

Tetsuya ARAKI, Koji M. KOBAYASHI

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.10 pp.1885-1887

Publication Date: 2016/10/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E99.A.1885

Type of Manuscript: LETTER

Category: Algorithms and Data Structures

Authors

Tetsuya ARAKI
the National Institute of Informatics
Koji M. KOBAYASHI
the National Institute of Informatics

Keyword

interval coloring, unit interval, online problem, interval graph

Cite this

Copy

Tetsuya ARAKI, Koji M. KOBAYASHI, "A Tight Analysis of Kierstead-Trotter Algorithm for Online Unit Interval Coloring" in IEICE TRANSACTIONS on Fundamentals, vol. E99-A, no. 10, pp. 1885-1887, October 2016, doi: 10.1587/transfun.E99.A.1885.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1885/_p

Copy

@ARTICLE{e99-a_10_1885,
author={Tetsuya ARAKI, Koji M. KOBAYASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Tight Analysis of Kierstead-Trotter Algorithm for Online Unit Interval Coloring},
year={2016},
volume={E99-A},
number={10},
pages={1885-1887},
abstract={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.},
keywords={},
doi={10.1587/transfun.E99.A.1885},
ISSN={1745-1337},
month={October},}

Copy

TY - JOUR
TI - A Tight Analysis of Kierstead-Trotter Algorithm for Online Unit Interval Coloring
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1885
EP - 1887
AU - Tetsuya ARAKI
AU - Koji M. KOBAYASHI
PY - 2016
DO - 10.1587/transfun.E99.A.1885
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2016
AB - 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.
ER -