On the span in channel assignment problems: Bounds, computing and counting (Q1810659)

The channel assignment problem involves assigning radio channels to transmitters, using a small span of channels but without causing excessive interference. In this paper a standard model for channel assignment, called the constraint matrix model, is considered, which extends ideas of graph colouring. Given a graph \(G=(V,E)\) and a length \(l(uv)\) for each edge \(uv\) of \(G\), an assignment \(\varphi :V \rightarrow \{1,\ldots ,t\}\) is called feasible if \(|\varphi (u)-\varphi (v)|\geq l(uv)\) for each edge \(uv\). The least \(t\) for which there is a feasible assignment is called the span of the problem. Two bounds on the span, an upper bound (from a sequential assignment method) and a lower bound are derived. It is shown that an extension of the Gallai-Roy theorem on the chromatic number and orientations allows us to calculate the span in \(O(n!)\) steps for a graph with \(n\) vertices, neglecting a polynomial factor. It is proved that, if the edge-lengths are bounded, then the span may be calculated in exponential time, that is, in time \(O(c^{n})\) for a constant \(c\). Finally, counting feasible assignments and related quantities are considered.