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

DOI10.1016/J.TCS.2004.04.017MaRDI QIDQ1770372zbMATH OpenOpenAlexFDO

Authors Dariusz R. Kowalski, Andrzej Pelc

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

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

Recommendations

• Broadcasting in undirected ad hoc radio networks
• Broadcasting in undirected ad hoc radio networks
• Broadcasting algorithms in radio networks with unknown topology
• Faster Deterministic Broadcasting in Ad Hoc Radio Networks
• Time of Deterministic Broadcasting in Radio Networks with Local Knowledge

Cites work

• scientific article; zbMATH DE number 1670865 (Why is no real title available?)
• scientific article; zbMATH DE number 1962806 (Why is no real title available?)
• scientific article; zbMATH DE number 1875436 (Why is no real title available?)
• scientific article; zbMATH DE number 910916 (Why is no real title available?)
• A lower bound for radio broadcast
• A new distributed depth-first-search algorithm
• An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
• Broadcasting in undirected ad hoc radio networks
• Deterministic broadcasting in ad hoc radio networks
• Families of finite sets in which no set is covered by the union of \(r\) others
• Faster broadcasting in unknown radio networks
• Lower bounds for the broadcast problem in mobile radio networks
• Nonrandom binary superimposed codes
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Selective families, superimposed codes, and broadcasting on unknown radio networks. (Extended abstract)

Cited in

(17)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1770372)