On the span in channel assignment problems: Bounds, computing and counting
The channel assignment problem involves assigning radio channels to transmitters, using a small span of channels but without causing excessive interference. We consider a standard model for channel assignment, the constraint matrix model, which extends ideas of graph colouring. Given a graph G=(V,E)...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2003
|
| _version_ | 1826263172769644544 |
|---|---|
| author | McDiarmid, C |
| author_facet | McDiarmid, C |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | The channel assignment problem involves assigning radio channels to transmitters, using a small span of channels but without causing excessive interference. We consider a standard model for channel assignment, the constraint matrix model, which extends ideas of graph colouring. Given a graph G=(V,E) and a length l(uv) for each edge uv of G, we call an assignment φ:V→{1,t} feasible if |φ(u)-φ(v)|l(uv) for each edge uv. The least t for which there is a feasible assignment is the span of the problem. We first derive two bounds on the span, an upper bound (from a sequential assignment method) and a lower bound. We then see that an extension of the Gallai-Roy theorem on chromatic number and orientations shows that the span can be calculated in O(n!) steps for a graph with n nodes, neglecting a polynomial factor. We prove that, if the edge-lengths are bounded, then we may calculate the span in exponential time, that is, in time O(c n) for a constant c. Finally we consider counting feasible assignments and related quantities. © 2003 Elsevier Science B.V. All rights reserved. |
| first_indexed | 2024-03-06T19:47:30Z |
| format | Journal article |
| id | oxford-uuid:22d28abc-8856-4ee2-a6dd-7f0c6c2e1dc5 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:47:30Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | oxford-uuid:22d28abc-8856-4ee2-a6dd-7f0c6c2e1dc52022-03-26T11:40:48ZOn the span in channel assignment problems: Bounds, computing and countingJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:22d28abc-8856-4ee2-a6dd-7f0c6c2e1dc5EnglishSymplectic Elements at Oxford2003McDiarmid, CThe channel assignment problem involves assigning radio channels to transmitters, using a small span of channels but without causing excessive interference. We consider a standard model for channel assignment, the constraint matrix model, which extends ideas of graph colouring. Given a graph G=(V,E) and a length l(uv) for each edge uv of G, we call an assignment φ:V→{1,t} feasible if |φ(u)-φ(v)|l(uv) for each edge uv. The least t for which there is a feasible assignment is the span of the problem. We first derive two bounds on the span, an upper bound (from a sequential assignment method) and a lower bound. We then see that an extension of the Gallai-Roy theorem on chromatic number and orientations shows that the span can be calculated in O(n!) steps for a graph with n nodes, neglecting a polynomial factor. We prove that, if the edge-lengths are bounded, then we may calculate the span in exponential time, that is, in time O(c n) for a constant c. Finally we consider counting feasible assignments and related quantities. © 2003 Elsevier Science B.V. All rights reserved. |
| spellingShingle | McDiarmid, C On the span in channel assignment problems: Bounds, computing and counting |
| title | On the span in channel assignment problems: Bounds, computing and counting |
| title_full | On the span in channel assignment problems: Bounds, computing and counting |
| title_fullStr | On the span in channel assignment problems: Bounds, computing and counting |
| title_full_unstemmed | On the span in channel assignment problems: Bounds, computing and counting |
| title_short | On the span in channel assignment problems: Bounds, computing and counting |
| title_sort | on the span in channel assignment problems bounds computing and counting |
| work_keys_str_mv | AT mcdiarmidc onthespaninchannelassignmentproblemsboundscomputingandcounting |