id: 02021229
dt: j
an: 02021229
au: McDiarmid, Colin; Reed, Bruce
ti: Channel assignment on graphs of bounded treewidth.
so: Discrete Math. 273, No.1-3, 183-192 (2003).
py: 2003
pu: Elsevier Science B.V. (North-Holland), Amsterdam
la: EN
cc: G.2.2
ut: Channel assignment; Bounded treewidth; Graph colouring
ci: 
li: doi:10.1016/S0012-365X(03)00236-X
ab: Summary: 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,\dots ,B$ such that $|ϕ(x)-ϕ(y)|\geqslant
    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.
rv: