Konrad-Zuse-Zentrum
|
ZIB PaperWeb
|
|
|
| 00-47 | Andreas Eisenblätter, Martin Grötschel, Arie M.C.A. Koster
Frequency Planning and Ramifications of Coloring Appeared in: Discussiones Mathematicae, Graph Theory 22 (2002) 51-88 |   |
Abstract:
This paper surveys frequency assignment problems coming up in planning
wireless communication services. It particularly focuses on cellular
mobile phone systems such as GSM, a technology that revolutionizes
communication. Traditional vertex coloring provides a conceptual
framework for the mathematical modeling of many frequency planning
problems. This basic form, however, needs various extensions to cover
technical and organizational side constraints. Among these ramifications
are 
-coloring and list coloring. To model all the subtleties, the
techniques of integer programming have proven to be very useful.
The ability to produce good frequency plans in practice is essential for
the quality of mobile phone networks. The present algorithmic solution
methods employ variants of some of the traditional coloring heuristics as
well as more sophisticated machinery from mathematical programming. This
paper will also address this issue.
Finally, this paper discusses several practical frequency assignment
problems in detail, states the associated mathematical models, and also
points to public electronic libraries of frequency assignment problems
from practice. The associated graphs have up to several thousand nodes
and range from rather sparse to almost complete.
Keywords: frequency assignment,
graph coloring
MSC: 05-02, 05C90, 90-02, 05C15