Radio communication in random graphs

Robert Elsässer, Leszek Gasieniec

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. We propose here several time efficient, centralized as well as fully distributed procedures for the broadcasting problem in random radio networks. In particular, we show how to perform a centralized broadcast in a random graph Gp = ( V, E ) of size n = | V | and expected average degree d = pn in time O ( ln n / ln d + ln d ). Later we present a randomized distributed broadcasting algorithm with the running time O ( ln n ). In both cases we show that the presented algorithms are asymptotically optimal by deriving lower bounds on the complexity of radio broadcasting in random graphs. In these proofs we determine some structural properties of random graphs and develop new techniques which might be useful for further research in this field. We should note here that the results of this paper hold with probability 1 - o ( 1 / n ).

Original languageEnglish (US)
Pages (from-to)490-506
Number of pages17
JournalJournal of Computer and System Sciences
Issue number3
StatePublished - May 1 2006
Externally publishedYes
EventSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - Las Vegas, NV, United States
Duration: Jul 18 2005Jul 20 2005


  • Broadcasting
  • Communication algorithms
  • Radio networks
  • Random graphs

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'Radio communication in random graphs'. Together they form a unique fingerprint.

Cite this