مشاهده مشخصات مقاله
Online Coloring Co-interval Graphs
|
Authors |
|
|
Conference |
دوازدهمین کنفرانس بینالمللی سالانه انجمن کامپیوتر ایران |
|
Abstract |
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 online algorithm in some arbitrary order, and the algorithm must assign
each interval a color that is di®erent from the colors of all previously presented intervals not intersecting
the current interval. 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 e®ect of randomization in our problem, and prove 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 competitive ratio better than 3/2. |
|
قیمت |
-
برای اعضای سایت : 100,000 Rial
-
برای دانشجویان عضو انجمن : 20,000 Rial
-
برای اعضای عادی انجمن : 40,000 Rial
|
خرید مقاله
|
|
.gif){kind=icon}