소출력 라디오 방송의 주파수 할당

Frequency A ssign m ent of L ow Power F M Broadcasting

We present a constraint satisfaction problem modeling and algorithms to solve a frequency assignment problem for low power FM broadcasting. Our research objective is to find a frequency assignment that satisfies all the constraints using minimum number of frequencies while maximizing the number of radio stations served for a given area. To get a good suboptimal solution, some variable ordering heuristics such as Dsatur variable ordering and most-used value ordering rule are provided. They enforce the backtracking process in a constraint satisfaction proDlem，so both the search space and computing time are greatly reduced. A lot of outstanding work on graph coloring problems has been achieved, and the theoretical lower bound of the chromatic number of random graph is one of them. Comparison between the theoretical lower bound and our computed approximate solution has been made for evaluation of proposed algorithm.