Online Coloring Co-interval Graphs

• fiche de synthèse - matière potentielle : the results

Online Coloring Co-interval Graphs∗ Hamid Zarrabi-Zadeh School of Computer Science, University of Waterloo Waterloo, Ontario, Canada, N2L 3G1 Abstract We study the problem of online coloring co-interval graphs. In this problem, a set of intervals on the real line is presented to the algorithm one at a time, and upon receiving each interval I, the algorithm must assign I a color different from the colors of all previously presented intervals not intersecting I. The objective is to use as few colors as possible.

• input sequences
• lb ub lb ub
• interval graph
• maximum clique size of the graph
• elementary graph theory
• online algorithm
• competitive ratio
• algorithm
• -1 unit
• unit