\input zb-basic
\input zb-ioport
\iteman{io-port 06084815}
\itemau{Katz, Matthew J.; Lev-Tov, Nissan; Morgenstern, Gila}
\itemti{Conflict-free coloring of points on a line with respect to a set of intervals.}
\itemso{Comput. Geom. 45, No. 9, 508-514 (2012).}
\itemab
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)$.
\itemrv{~}
\itemcc{}
\itemut{conflict-free coloring; frequency assignment; approximation algorithms}
\itemli{doi:10.1016/j.comgeo.2012.01.013}
\end