On the complexity of bandwidth allocation in radio networks
DOI10.1016/J.TCS.2008.06.048zbMATH Open1217.68040OpenAlexW1980677244MaRDI QIDQ952444FDOQ952444
Authors: Ralf Klasing, Nelson Morales, Stéphane Pérennes 
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
Recommendations
- Round weighting problem and gathering in radio networks with symmetrical interference
- Bandwidth allocation in cellular networks with multiple interferences
- scientific article; zbMATH DE number 17557
- Approximation algorithms for channel assignment with constraints
- scientific article; zbMATH DE number 1263991
approximation algorithmsbandwidth allocationradio networksmaximum concurrent flowsteady state traffic
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)
Cites Work
- The ellipsoid method and its consequences in combinatorial optimization
- Unit disk graphs
- Geometric algorithms and combinatorial optimization.
- Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
- A characterization of perfect graphs
- Fundamentals of Wireless Communication
- The maximum concurrent flow problem
- Approximation schemes for covering and packing problems in image processing and VLSI
- Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
- Title not available (Why is that?)
- NP-completeness of some generalizations of the maximum matching problem
- Zero knowledge and the chromatic number
- The strong chromatic index ofC4-free graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Coloring a Family of Circular Arcs
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Title not available (Why is that?)
- Fast approximation algorithms for multicommodity flow problems
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
- Gathering Algorithms on Paths Under Interference Constraints
- Lower bounds on systolic gossip
- The complexity of systolic dissemination of information in interconnection networks
- An approximation algorithm for circular arc colouring
Cited In (18)
- GATHERING RADIO MESSAGES IN THE PATH
- A strongly polynomial algorithm for the minimum maximum flow degree problem
- Linear time computation of the maximal linear and circular sums of multiple independent insertions into a sequence
- Optimal gathering protocols on paths under interference constraints
- Congestion, dilation, and energy in radio networks
- Gossiping with interference in radio ring networks
- Bounding the maximum size of a packet radio network
- The proportional coloring problem: optimizing buffers in radio mesh networks
- On the complexity of connectivity in cognitive radio networks through spectrum assignment
- Dynamic Spectrum Management: A Complete Complexity Characterization
- Optimal gathering in radio grids with interference
- Using the minimum maximum flow degree to approximate the flow coloring problem
- Bandwidth allocation in cellular networks with multiple interferences
- Round weighting problem and gathering in radio networks with symmetrical interference
- On the complexity of the flow coloring problem
- Distributed link scheduling in wireless networks
- Cross line and column generation for the cut covering problem in wireless networks
- The backbone coloring problem for bipartite backbones
This page was built for publication: On the complexity of bandwidth allocation in radio networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q952444)
