Graph theoretic approach to the channel assignment problem in cellular systems

Generally, the channel assignment problem (CAP) for mobile cellular systems is solved by graph coloring algorithms. These algorithms, though sometimes can yield optimal solution, do not supply any information on how far away it is from the optimum or on which situations an optimal solution can be found. In view of these undersirable features, two relevant results are presented in this paper. First of all, a lower bound for the minimum number of total channels required for the fulfillment of the demand of each cell is derived. This lower bound is tighter than the existing ones under certain conditions and can be used as a supplement of those approximate algorithms. Secondly, we propose an efficient algorithm to solve this problem. Though the CAP is NP-complete in general, our algorithm provides optimal solution for a special class of networks. For the general case, promising results are obtained and numerical examples show that our algorithm has a better performance than the existing algorithms.