Abstract | ||
---|---|---|
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(cn) for a constant c. Finally we consider counting feasible assignments and related quantities. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1016/S0012-365X(02)00821-X | Discrete Mathematics |
Keywords | Field | DocType |
lower bound,standard model,polynomial factorization,upper bound | Graph theory,Discrete mathematics,Standard Model,Combinatorics,Exponential function,Polynomial,Upper and lower bounds,Communication channel,Interference (wave propagation),Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
266 | 1-3 | 0012-365X |
Citations | PageRank | References |
26 | 1.64 | 6 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Colin McDiarmid | 1 | 1071 | 167.05 |