The on-line first-fit algorithm for radio frequency assignment problems
The radio frequency assignment problem is to minimize the number of frequencies used by transmitters with no interference in radio communication networks; it can be modeled as the minimum vertex coloring problem on unit disk graphs. In this paper, we consider the on-line first-fit algorithm for the problem and show that the competitive ratio of the algorithm for the unit disk graph G with chi (G) = 2 is 3, where chi (G) is the chromatic number of G. Moreover, the competitive ratio of the algorithm for the unit disk graph G with chi (G) > 2 is at least 4 - 3/chi(G). The average performance for the algorithm is also discussed in this paper. (C) 2002 Elsevier Science B.V. All rights reserved.
radio frequency assignment problems unit disk graphs graph coloring problems on-line algorithms