Strong conflict-free coloring for intervals

DOI10.1007/978-3-642-35261-4_4MaRDI QIDQ4909516zbMATH OpenOpenAlexFDO

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)

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

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)

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.

Recommendations

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)