A tight analysis of Kierstead-Trotter algorithm for online unit interval coloring

Kierstead and Trotter (Congressus Numerantium 33, 1981) proved that their algorithm is an optimal online algorithm for the online interval coloring problem. In this paper, for online unit interval coloring, we show that the number of colors used by the Kierstead-Trotter algorithm is at most \(3 \ome...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-09
Main Authors: Araki, Tetsuya, Kobayashi, Koji M
Format: Article
Language:English
Subjects:
Algorithms
Coloring
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Kierstead and Trotter (Congressus Numerantium 33, 1981) proved that their algorithm is an optimal online algorithm for the online interval coloring problem. In this paper, for online unit interval coloring, we show that the number of colors used by the Kierstead-Trotter algorithm is at most \(3 \omega(G) - 3\), where \(\omega(G)\) is the size of the maximum clique in a given graph \(G\), and it is the best possible.
ISSN:2331-8422
DOI:10.48550/arxiv.1609.09031