Conference icon

Conference

Channel assignment on graphs of bounded treewidth.

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 φ(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 o...

Expand abstract
Publication status:
Published

Actions


Access Document


Authors


McDiarmid, C More by this author
Volume:
273
Issue:
1-3
Pages:
183-192
Publication date:
2003
DOI:
ISSN:
0012-365X
URN:
uuid:9793acba-8dbe-4042-ba68-ecd5c6197f96
Source identifiers:
102297
Local pid:
pubs:102297

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP