Approximation algorithms for channel assignment with constraints (Q5958140): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Colouring weighted bipartite graphs with a co-site constraint / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Adaptive multicolouring / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Channel assignment and weighted coloring / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Corrigendum: Static frequency assignment in cellular networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Online channel allocation in FDMA networks with reuse constraints / rank | |||
Normal rank |
Revision as of 23:20, 3 June 2024
scientific article; zbMATH DE number 1715106
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximation algorithms for channel assignment with constraints |
scientific article; zbMATH DE number 1715106 |
Statements
Approximation algorithms for channel assignment with constraints (English)
0 references
3 March 2002
0 references
Cellular networks are generally modeled as node-weighted graphs, where the nodes represent cells and the edges represent the possibility of radio interference. An algorithm for the channel assignment problem must assign as many channels as the weight indicates to every node, such that any two channels assigned to the same node satisfy the co-site constraint, and any two channels assigned to adjacent nodes satisfy the inter-site constraint. We describe several approximation algorithms for channel assignment with arbitrary co-site and inter-site constraints for odd cycles and the so-called hexagon graphs that are often used to model cellular networks. The algorithms given for odd cycles are optimal for some values of constraints, and have performance ratio at most \(1+1/(n-1)\) for all other cases, where \(n\) is the length of the cycle. Our main result is an algorithm of performance ratio at most \(\frac 43+\frac{1}{100}\) for hexagon graphs with arbitrary co-site and inter-site constraints.
0 references
frequency assignment
0 references
approximation algorithms
0 references
radio colouring
0 references