TY - JOUR
ID - 3228
TI - Online Coloring Co-Interval Graphs
JO - Scientia Iranica
JA - SCI
LA - en
SN - 1026-3098
AU - Zarrabi-Zadeh, H.
AD - Department of Computer Science,Berakly
Y1 - 2009
PY - 2009
VL - 16
IS - 1
SP -
EP -
KW - Online algorithms
KW - Graph coloring
KW - Co-interval graphs
DO -
N2 - 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 dierent from the colors of all previously presented intervals not
intersecting I. The objective is to use as few colors as possible. It is known that the competitive ratio of
the simple FIRST-FIT algorithm on the class of co-interval graphs is at most 2. We show that for the
class of unit co-interval graphs, where all intervals have equal length, the 2-bound on the competitive ratio
of FIRST-FIT is tight. On the other hand, we show that no deterministic online algorithm for coloring
unit co-interval graphs can be better than 3/2-competitive. We then study the eect of randomization on
our problem and show a lower bound of 4/3 on the competitive ratio of any randomized algorithm for
the unit co-interval coloring problem. We also prove that for the class of general co-interval graphs, no
randomized algorithm has a competitive ratio better than 3/2.
UR - https://scientiairanica.sharif.edu/article_3228.html
L1 - https://scientiairanica.sharif.edu/article_3228_532d1a3203a001998fd85caf90d82f7c.pdf
ER -