zbMATH — the first resource for mathematics

Frequency planning and ramifications of coloring. (English) Zbl 1055.05147
The paper deals with frequency assignment problems (FAPs) appearing in planning of wireless communication services. The authors describe the GSM standard, FAPs which are related to GSM and their combinatorial models (vertex colorings, \(T\)-coloring, list \(T\)-coloring, set \(T\)-coloring and integer programming). These models are then discussed from the computational point of view. The authors present the computational complexity of the models (all of them are NP-hard, some are NP-hard in the strong sense), heuristics used to solve them (e.g., greedy algorithm) and their practical instances. The paper ends with a survey of lower bounds for the span and the other parameters associated with combinatorial models of FAPs.

05C90 Applications of graph theory
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
05C15 Coloring of graphs and hypergraphs
68R10 Graph theory (including graph drawing) in computer science
FASoft; SeDuMi
Full Text: DOI