Logarithmic inapproximability of the radio broadcast problem

DOI10.1016/j.jalgor.2003.11.004zbMath1090.68048OpenAlexW2002226487MaRDI QIDQ4828562

Michael Elkin, Guy Kortsarz

Publication date: 23 November 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2003.11.004

zbMATH Keywords

set-cover problemlabel-cover problem

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Optimal deterministic broadcasting in known topology radio networks, Faster communication in known topology radio networks, GATHERING RADIO MESSAGES IN THE PATH, Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks, Many-to-many communication in radio networks, Time-Efficient Broadcast in Radio Networks, Optimal gathering protocols on paths under interference constraints