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

Mathematics Subject Classification ID

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)

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

Cited in

(8)

• Faster communication in known topology radio networks
• Optimal deterministic broadcasting in known topology radio networks
• Logarithmic inapproximability of the radio broadcast problem
• Time-efficient broadcast in radio networks
• Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem
• Near-optimal radio use for wireless network synchronization
• Upper and lower bounds for deterministic broadcast in powerline communication networks
• Feasibility and complexity of broadcasting with random transmission failures

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)