Frequency planning and ramifications of coloring. (English) Zbl 1055.05147

Eisenblätter, Andreas; Grötschel, Martin; Koster, Arie M. C. A.

Discuss. Math., Graph Theory 22, No. 1, 51-88 (2002).

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.

Reviewer: Marek Kubale (Gdańsk)

MSC:

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

Keywords:

graph coloring; frequency assignment; span of coloring

Software:

FASoft; SeDuMi