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 on 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 approximation algorithm for the general problem; the algorithm has approximation ratio 2 when k = 1 and 5 − 2k when k ≥ 2. 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 provide, in case k = O(polylog(n)), a quasipolynomial time algorithm to decide the existence of a k-SCF coloring that uses at most q colors.

Strong Conflict-Free Coloring for Intervals

GARGANO, Luisa;RESCIGNO, Adele Anna;
2014

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 on 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 approximation algorithm for the general problem; the algorithm has approximation ratio 2 when k = 1 and 5 − 2k when k ≥ 2. 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 provide, in case k = O(polylog(n)), a quasipolynomial time algorithm to decide the existence of a k-SCF coloring that uses at most q colors.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/4465857
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 11
social impact