On the complexity of bandwidth allocation in radio networks

DOI10.1016/j.tcs.2008.06.048zbMath1217.68040OpenAlexW1980677244MaRDI QIDQ952444

Ralf Klasing, Stéphane Pérennes, Nelson Morales

Publication date: 12 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.06.048

zbMATH Keywords

approximation algorithmsbandwidth allocationradio networksmaximum concurrent flowsteady state traffic

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (13)

Cross line and column generation for the cut covering problem in wireless networks ⋮ THE PROPORTIONAL COLORING PROBLEM: OPTIMIZING BUFFERS IN RADIO MESH NETWORKS ⋮ Round weighting problem and gathering in radio networks with symmetrical interference ⋮ Using the minimum maximum flow degree to approximate the flow coloring problem ⋮ A strongly polynomial algorithm for the minimum maximum flow degree problem ⋮ Bandwidth allocation in cellular networks with multiple interferences ⋮ The backbone coloring problem for bipartite backbones ⋮ On the complexity of the flow coloring problem ⋮ Linear time computation of the maximal linear and circular sums of multiple independent insertions into a sequence ⋮ GATHERING RADIO MESSAGES IN THE PATH ⋮ Optimal gathering in radio grids with interference ⋮ Optimal gathering protocols on paths under interference constraints ⋮ Distributed link scheduling in wireless networks

Cites Work

• Unnamed Item
• Unnamed Item
• The ellipsoid method and its consequences in combinatorial optimization
• NP-completeness of some generalizations of the maximum matching problem
• Unit disk graphs
• Zero knowledge and the chromatic number
• Geometric algorithms and combinatorial optimization.
• Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
• Lower bounds on systolic gossip
• Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
• Fast approximation algorithms for multicommodity flow problems
• A characterization of perfect graphs
• Gathering Algorithms on Paths Under Interference Constraints
• The maximum concurrent flow problem
• Approximation schemes for covering and packing problems in image processing and VLSI
• Coloring a Family of Circular Arcs
• Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
• The complexity of systolic dissemination of information in interconnection networks
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• The strong chromatic index ofC4-free graphs
• Fundamentals of Wireless Communication
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• An approximation algorithm for circular arc colouring

This page was built for publication: On the complexity of bandwidth allocation in radio networks