Fast broadcasting and gossiping in radio networks

Marek Chrobak, Leszek Ga̧sieniec, Wojciech Rytter

Research output: Contribution to journalArticlepeer-review

123 Scopus citations


We establish an O(n log2 n) upper bound on the time for determineistic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(n log n). The fastest previously known algorithm for this problem works in tome O(n3/2). Using our broadcasting algorithm, we develop an O(n3/2 log2 n) algorithm for gossiping in the same network model.

Original languageEnglish (US)
Pages (from-to)177-189
Number of pages13
JournalJournal of Algorithms
Issue number2
StatePublished - May 2002
Externally publishedYes

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Fast broadcasting and gossiping in radio networks'. Together they form a unique fingerprint.

Cite this