Conflict-Free Coloring of points on a line with respect to a set of intervals
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 ) .
conflict-free coloring approximation algorithms frequency assignment