We consider the k-strong conflict-free (k-SCF) coloring of a set of points on a line with respect to a family of intervals: Each point non the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval I of the family there are at least k colors each appearing exactly once in I. We first present a polynomial time algorithm for the general problem; the algorithm has approximation ratio 2 when k = 1 and 5 − 2k when k > 1 (our analysis is tight). In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any k ≥ 1. We also show that the problem of deciding whether a given family of intervals can be 1-SCF colored with at most q colors has a quasipolynomial time algorithm.
Strong Conflict-Free Coloring for Intervals
GARGANO, Luisa;RESCIGNO, Adele Anna;
2012-01-01
Abstract
We consider the k-strong conflict-free (k-SCF) coloring of a set of points on a line with respect to a family of intervals: Each point non the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval I of the family there are at least k colors each appearing exactly once in I. We first present a polynomial time algorithm for the general problem; the algorithm has approximation ratio 2 when k = 1 and 5 − 2k when k > 1 (our analysis is tight). In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any k ≥ 1. We also show that the problem of deciding whether a given family of intervals can be 1-SCF colored with at most q colors has a quasipolynomial time algorithm.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
