Name
Abstract | ||
|---|---|---|
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 @f(x) from 1,...,B such that |@f(x)-@f(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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0012-365X(03)00236-X | Discrete Mathematics |
Keywords | Field | DocType |
bounded treewidth,channel assignment,graph colouring,communication system,fully polynomial time approximation scheme | Discrete mathematics,Indifference graph,Combinatorics,Tree-depth,Partial k-tree,Bipartite graph,Chordal graph,Clique-sum,Treewidth,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
273 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
11 | 0.96 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin McDiarmid | 1 | 1071 | 167.05 |
| Bruce Reed | 2 | 11 | 0.96 |