id: 06084815
dt: j
an: 06084815
au: Katz, Matthew J.; Lev-Tov, Nissan; Morgenstern, Gila
ti: Conflict-free coloring of points on a line with respect to a set of
    intervals.
so: Comput. Geom. 45, No. 9, 508-514 (2012).
py: 2012
pu: Elsevier Science B.V. (North-Holland), Amsterdam
la: EN
cc: 
ut: conflict-free coloring; frequency assignment; approximation algorithms
ci: 
li: doi:10.1016/j.comgeo.2012.01.013
ab: Summary: We present approximation algorithms for CF-coloring of points on a
    line with respect to a given set of intervals. For the restricted case
    where no two intervals have a common right endpoint, we present a
    2-approximation algorithm, and, for the general case where intervals
    may share a right endpoint, we present a 4-approximation algorithm. The
    running time of both algorithms is $O(n \log n)$.
rv: