Discrete mathematics and radio channel assignment (Q4407445)

This is a survey on a variety of graph-theoretic problems, which are motivated by the problem of assigning channels for cellular radiocommunications problems. The graph-theoretic problems turn out to be variants or generalizations of classical problems in graph coloring. The following is a paradigmatic problem: we are given a graph, and a non-negative integer, the length \(l(e)\), assigned to each edge \(e.\) The vertices need to be colored with \(t\) colours, where the colours are the first \(t\) natural numbers, in such a way that for each edge \(e\) the colours of its vertices differ by at least \(l(e).\) The aim is to minimize \(t.\) In the application the vertices are network sites, the edge lengths represent the minimal channel seperation to avoid interference, and \(t\) is the number of channels needed. For the entire collection see [Zbl 1005.00014].