Channel assignment on graphs of bounded treewidth.

The following 'constraint matrix span problem' arises in the assignment of radio channels in cellular communications systems. Given a graph G with a positive integer length l(xy) for each edge xy, and given a positive integer B, can we assign to each vertex x a channel φ(x) from 1,...,B such that |φ(x) - φ(y)|≥l(xy) for each edge xy? We show that this problem is NP-complete for graphs of treewidth at most 3, but there is a fully polynomial time approximation scheme for the problem on graphs of bounded treewidth. We see also that it is NP-complete for graphs which can be made bipartite by deleting a single vertex. © 2003 Elsevier B.V. All rights reserved