2012/05/09 by Luisa Gargano, Gargano, Luisa, Adele A. Rescigno +1
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1205.1900
openalex publication_date 2012/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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≥2 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≥1.