Frequency Planning and Ramifications of Coloring

Please always quote using this URN: urn:nbn:de:0297-zib-6152
  • 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 nodes and range from rather sparse to almost complete.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Andreas Eisenblätter, Martin Grötschel, Arie M.C.A. Koster
Document Type:ZIB-Report
Tag:frequency assignment; graph coloring
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05-02 Research exposition (monographs, survey articles)
05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C15 Coloring of graphs and hypergraphs
05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C90 Applications [See also 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-02 Research exposition (monographs, survey articles)
Date of first Publication:2000/12/12
Series (Serial Number):ZIB-Report (00-47)
Published in:Appeared in: Discussiones Mathematicae, Graph Theory 22 (2002) 51-88