%0 Journal Article
%T Strong Conflict-Free Coloring of Intervals
%A Luisa Gargano
%A Adele A. Rescigno
%J Computer Science
%D 2012
%I arXiv
%X We consider the k-strong conflict-free coloring of a set of points on a line with respect to a family of intervals: Each point on the line must be assigned a color so that the coloring has to be conflict-free, in the sense that in every interval I there are at least k colors each appearing exactly once in I. In this paper, we present a polynomial algorithm for the general problem; the algorithm has an approximation factor 5-2/k when k\geq2 and approximation factor 2 for k=1. In the special case the family contains all the possible intervals on the given set of points, we show that a 2 approximation algorithm exists, for any k\geq1.
%U http://arxiv.org/abs/1205.1900v1