Frequency assignment: Theory and applications

TLDR

Disk graphs are central to frequency‑distance constrained frequency assignment problems. The paper introduces a minimum‑order frequency‑assignment approach, generalizes chromatic number, and explores real‑world applications and future research directions. The authors model frequency assignment as both frequency‑distance constrained and frequency‑constrained optimization problems. The minimum‑order approach is potentially more desirable, the frequency‑constrained method should be avoided when distance separation is used, and many problems are classified by algorithmic execution‑time efficiency.

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.