Let H= (V, E) be a hypergraph. A k-strong conflict-free coloring of H is an assignment of colors to the members of the vertex set V such that every hyperedge E â Îµ, |E| â¥ k, contains k nodes whose colors are pairwise distinct and different from the colors assigned to all the other nodes in E, whereas if | E| < k all nodes in E get distinct colors. The parameter to optimize is the total number of colors. The need for such colorings originally arose as a problem of frequency assignment for cellular networks, but since then it has found applications in a variety of different areas. In this paper we consider a generalization of the above problem, where one is allowed to assign more than one color to each node. When k= 1, our generalization reduces to the conflict-free multicoloring problem introduced by Even et al. , and recently studied by BÃ¤rtschi and Grandoni , and Ghaffari et al. . We motivate our generalized formulation and we point out that it includes a vast class of well known combinatorial and algorithmic problems, when the hypergraph H and the parameter k are properly instantiated. Our main result is an algorithm to construct a k-strong conflict-free multicolorings of an input hypergraph H that utilizes a total number of colors O(min(k+log(r/k))logÎ+k(k+log2(r/k)),(k2+r)logn), where n is the number of nodes, r is the maximum hyperedge size, and Î is the maximum hyperedge degree; the expected number of colors per node is O(mink+logÎ,(k+log(r/k))logn). Although derived for arbitrary k, our result improves on the corresponding result by BÃ¤rtschi and Grandoni , when instantiated for k= 1. We also provide lower bounds on the number of colors needed in any k-strong conflict-free multicoloring, thus showing that our algorithm is not too far from being optimal.
|Titolo:||On k-strong conflict-free multicoloring|
|Data di pubblicazione:||2017|
|Appare nelle tipologie:||4.1 Contributi in Atti di convegno|