Deterministic conflict-free coloring for intervals: from offline to online Academic Article uri icon


  • Abstract We investigate deterministic algorithms for a frequency assignment problem in cellular networks. The problem can be modeled as a special vertex coloring problem for hypergraphs: In every hyperedge there must exist a vertex with a color that occurs exactly once in the hyperedge (the conflict-free property). We concentrate on a special case of the problem, called conflict-free coloring for intervals. We introduce a hierarchy of four models for the aforesaid problem:(i) static,(ii) dynamic offline,(iii) dynamic online with absolute positions, and (iv) dynamic online with relative positions. In the dynamic offline model, we give a deterministic algorithm that uses at most log 3/2 n+ 1 &; approx; 1.71 log 2 n colors and show inputs that force any algorithm to use at least 3 log 5 n+ 1 ≈ 1.29 log 2 n colors. For the online absolute-positions model, we give a deterministic algorithm that …

publication date

  • January 1, 2008