Geodesic
Frequency planning and ramifications of coloring
Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 1, pp. 51-88

Voir la notice de l'article provenant de la source Library of Science

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 T-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 vertices and range form rather sparse to almost complete.
Keywords: frequency assignment, graph coloring 
@article{DMGT_2002_22_1_a5,
     author = {Eisenbl\"atter, Andreas and Gr\"otschel, Martin and Koster, Arie},
     title = {Frequency planning and ramifications of coloring},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {51--88},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a5/}
}
TY  - JOUR
AU  - Eisenblätter, Andreas
AU  - Grötschel, Martin
AU  - Koster, Arie
TI  - Frequency planning and ramifications of coloring
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2002
SP  - 51
EP  - 88
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a5/
LA  - en
ID  - DMGT_2002_22_1_a5
ER  - 
%0 Journal Article
%A Eisenblätter, Andreas
%A Grötschel, Martin
%A Koster, Arie
%T Frequency planning and ramifications of coloring
%J Discussiones Mathematicae. Graph Theory
%D 2002
%P 51-88
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a5/
%G en
%F DMGT_2002_22_1_a5
Eisenblätter, Andreas; Grötschel, Martin; Koster, Arie. Frequency planning and ramifications of coloring. Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 1, pp. 51-88. http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a5/