Conflict-free coloring for intervals: From offline to online Conference Paper uri icon


  • Abstract This paper studies deterministic algorithms for a frequency assignment problem in cellular networks. A cellular network consists of fixed-position base stations and moving agents. Each base station operates at a fixed frequency, and this allows an agent tuned at this frequency to communicate with the base station. Each agent has a specific range of communication (described as a geometric shape, eg, a disc) that may contain one or several base stations. To avoid interference, the goal is to assign frequencies to base stations such that for any range, there exists a base station in the range with a frequency that is not reused by some other base station in the range. The base station with this unique (in the range) frequency serves the aforementioned range. Since using many frequencies is expensive, the optimization goal is to use as few frequencies as possible. The problem can be …

publication date

  • January 1, 2006