- 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
- 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
- Copyright date:
- 2003
Conference
Channel assignment on graphs of bounded treewidth.
Actions
Authors
Bibliographic Details
Item Description
Terms of use
Metrics
Altmetrics
Dimensions
If you are the owner of this record, you can report an update to it here: Report update to this record