Channel assignment on graphs of bounded treewidth.

Conference item

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.

Authors: McDiarmid, C; Reed, B

• Publication status: Published
• Host title: Discrete Mathematics
• Volume: 273
• Issue: 1-3
• Pages: 183-192
• Publication date: 2003-01-01
• DOI: 10.1016/S0012-365X(03)00236-X
• ISSN: 0012-365X
• Keywords: channel assignment; graph colouring; bounded treewidth