Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism

DOI10.1016/j.tcs.2004.04.017zbMath1070.68009OpenAlexW1973843421MaRDI QIDQ1770372

Andrzej Pelc, Dariusz R. Kowalski

Publication date: 6 April 2005

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

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

zbMATH Keywords

RandomizationAdaptivenessRadio broadcasting

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Related Items (15)

Broadcasting in UDG radio networks with missing and inaccurate information ⋮ Broadcasting in UDG radio networks with unknown topology ⋮ Fault-tolerant aggregation: flow-updating meets mass-distribution ⋮ Acknowledged broadcasting and gossiping in ad hoc radio networks ⋮ Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony ⋮ Fast Radio Broadcasting with Advice ⋮ Activating anonymous ad hoc radio networks ⋮ Broadcasting in UDG Radio Networks with Missing and Inaccurate Information ⋮ The abstract MAC layer ⋮ Initializing sensor networks of non-uniform density in the weak sensor model ⋮ Fast radio broadcasting with advice ⋮ Improved lower bound for deterministic broadcasting in radio networks ⋮ Acknowledged broadcasting in ad hoc radio networks ⋮ Broadcasting in undirected ad hoc radio networks ⋮ Time-Efficient Broadcast in Radio Networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new distributed depth-first-search algorithm
• Families of finite sets in which no set is covered by the union of \(r\) others
• A lower bound for radio broadcast
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Faster broadcasting in unknown radio networks
• An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
• Lower bounds for the broadcast problem in mobile radio networks
• Deterministic broadcasting in ad hoc radio networks
• Nonrandom binary superimposed codes
• Broadcasting in undirected ad hoc radio networks

This page was built for publication: Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism