Weakening the online adversary just enough to get optimal conflict-free colorings for intervals Conference Paper uri icon


  • A hypergraph H=(V, E) is a generalization of a graph for which hyperedges (elements of E) can be arbitrary-sized non-empty subsets of the vertex set V. A vertex coloring C: V→ N+ of hypergraph H is called conflict-free if in every hyperedge e there is a vertex whose color is unique among all other colors in the hyperedge. The above problem models a frequency assignment problem for cellular networks. A cellular network consists of fixed-position base stations and moving agents. The study of conflict-free colorings was originated in the work of Even et al.[4] and Smorodinsky [6]. In addition to the practical motivation described above, this new coloring model has drawn much attention of researchers through its own theoretical interest and such colorings have been the focus of several recent papers. Chen et al.[3] considered the special case of the problem where the hypergraph is defined as follows …

publication date

  • January 1, 2007