DocumentCode :
961442
Title :
Frequency assignment: Theory and applications
Author :
Hale, William K.
Author_Institution :
ITS/NTIA, U. S. Department of Commerce, Boulder, CO
Volume :
68
Issue :
12
fYear :
1980
Firstpage :
1497
Lastpage :
1514
Abstract :
In this paper we introduce the minimum-order approach to frequency assignment and present a theory which relates this approach to the traditional one. This new approach is potentially more desirable than the traditional one. We model assignment problems as both frequency-distance constrained and frequency constrained optimization problems. The frequency constrained approach should be avoided if distance separation is employed to mitigate interference. A restricted class of graphs, called disk graphs, plays a central role in frequency-distance constrained problems. We introduce two generalizations of chromatic number and show that many frequency assignment problems are equivalent to generalized graph coloring problems. Using these equivalences and recent results concerning the complexity of graph coloring, we classify many frequency assignment problems according to the "execution time efficiency" of algorithms that may be devised for their solution. We discuss applications to important real world problems and identify areas for further work.
Keywords :
Bandwidth; Constraint optimization; Electromagnetic spectrum; Frequency; Interference constraints; Interference elimination; Radio transmitters; Radiofrequency identification; Telegraphy; US Department of Commerce;
fLanguage :
English
Journal_Title :
Proceedings of the IEEE
Publisher :
ieee
ISSN :
0018-9219
Type :
jour
DOI :
10.1109/PROC.1980.11899
Filename :
1456167
Link To Document :
بازگشت