On the span in channel assignment problems: Bounds, computing and counting (Q1810659): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on the complexity of the chromatic number problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Determining the Chromatic Number of a Graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Frequency-distance constraints with large distances / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4407445 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bounds for the frequency assignment problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Arrangements, channel assignments, and associated polynomials / rank | |||
Normal rank |
Latest revision as of 17:25, 5 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the span in channel assignment problems: Bounds, computing and counting |
scientific article |
Statements
On the span in channel assignment problems: Bounds, computing and counting (English)
0 references
9 June 2003
0 references
The channel assignment problem involves assigning radio channels to transmitters, using a small span of channels but without causing excessive interference. In this paper a standard model for channel assignment, called the constraint matrix model, is considered, which extends ideas of graph colouring. Given a graph \(G=(V,E)\) and a length \(l(uv)\) for each edge \(uv\) of \(G\), an assignment \(\varphi :V \rightarrow \{1,\ldots ,t\}\) is called feasible if \(|\varphi (u)-\varphi (v)|\geq l(uv)\) for each edge \(uv\). The least \(t\) for which there is a feasible assignment is called the span of the problem. Two bounds on the span, an upper bound (from a sequential assignment method) and a lower bound are derived. It is shown that an extension of the Gallai-Roy theorem on the chromatic number and orientations allows us to calculate the span in \(O(n!)\) steps for a graph with \(n\) vertices, neglecting a polynomial factor. It is proved that, if the edge-lengths are bounded, then the span may be calculated in exponential time, that is, in time \(O(c^{n})\) for a constant \(c\). Finally, counting feasible assignments and related quantities are considered.
0 references
channel assignment problem
0 references
constraint matrix model
0 references
graph colourig
0 references
span
0 references
Gallai-Roy theorem
0 references
chromatic number
0 references