|
|
|
|
Online conict-free coloring of intervals
|
|
|
|
|
|
|
|
نویسنده
|
Abam M.A. ,Rezaei Seraji M.J. ,Shadravan M.
|
|
منبع
|
scientia iranica - 2014 - دوره : 21 - شماره : 6-D2 - صفحه:2138 -2141
|
|
چکیده
|
In this paper, we study the problem of online conict-free coloring of intervals on a line, where each newly inserted interval must be assigned a color upon insertion such that the coloring remains conict-free, i.e. for each point p in the union of the current intervals, there must be an interval i with a unique color among all intervals covering p. we first present a simple algorithm which uses o(sqrt(n)) colors where n is the number of current intervals. next, we propose an cf-coloring of intervals which uses o(log^3 n) colors.
|
|
کلیدواژه
|
Frequency assignment; Conict-free coloring; Intervals; On-line algorithms; Computational geometry
|
|
آدرس
|
sharif university of technology, Department of Computer Engineering, ایران, sharif university of technology, Department of Computer Engineering, ایران, sharif university of technology, Department of Computer Engineering, ایران
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|