Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
DOI10.1007/B99805zbMATH Open1105.68302OpenAlexW4301133941MaRDI QIDQ5313014FDOQ5313014
Authors: Michael Elkin, Guy Kortsarz 
Publication date: 25 August 2005
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/b99805
Recommendations
- Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem
- Logarithmic inapproximability of the radio broadcast problem
- An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
- scientific article; zbMATH DE number 1670545
- A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10)
Cited In (8)
- Faster communication in known topology radio networks
- Feasibility and complexity of broadcasting with random transmission failures
- Near-optimal radio use for wireless network synchronization
- Logarithmic inapproximability of the radio broadcast problem
- Optimal deterministic broadcasting in known topology radio networks
- Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem
- Upper and lower bounds for deterministic broadcast in powerline communication networks
- Time-efficient broadcast in radio networks
This page was built for publication: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5313014)
