Frequency Assignment
Next: Register Allocation
Up: Sample Applications
Previous: Time Tabling and
Gamst [38] examines a
problem in assigning frequencies to mobile radios and other users of
the electromagnetic spectrum. In the simplest case, two customers
that are sufficiently close must be assigned different frequencies,
while those that are distant can share frequencies. The problem of
minimizing the number of frequencies is then a graph coloring problem.
If one considers situations where users (vertices) enter and leave
the system, this application also provides a setting where on-line
algorithms would be relevant.
Michael A. Trick
Thu Oct 27 21:43:48 EDT 1994