The on-line first-fit algorithm for radio frequency assignment problems |
| |
Authors: | Yin-Te Tsai Yaw-Ling Lin |
| |
Affiliation: | a Department of Computer Science and Information Management, Providence University, Taiwan, Republic of China b Department of Accounting, Providence University, Taiwan, Republic of China |
| |
Abstract: | 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 χ(G)=2 is 3, where χ(G) is the chromatic number of G. Moreover, the competitive ratio of the algorithm for the unit disk graph G with χ(G)>2 is at least 4−3/χ(G). The average performance for the algorithm is also discussed in this paper. |
| |
Keywords: | Unit disk graphs Radio frequency assignment problems Graph coloring problems On-line algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|