Strong conflict-free coloring for intervals

DOI10.1007/978-3-642-35261-4_4zbMATH Open1260.05158arXiv1205.1900OpenAlexW2179409935MaRDI QIDQ4909516FDOQ4909516

Authors: Panagiotis Cheilaris, Adele A. Rescigno, Luisa Gargano, Shakhar Smorodinsky

Publication date: 21 March 2013

Published in: Algorithms and Computation (Search for Journal in Brave)

Abstract: 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 kgeq2 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 kgeq1.

Full work available at URL: https://arxiv.org/abs/1205.1900

Recommendations

zbMATH Keywords

strong conflict free coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cited In (5)

This page was built for publication: Strong conflict-free coloring for intervals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909516)