An improved algorithm for radio broadcast

Michael Elkin, Guy Kortsarz

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We show that for every radio network G = (V, E) and source s ∈ V, there exists a radio broadcast schedule for G of length Rad(G, s) + O(√Rad(G, s) · log2 n) = O(Rad(G, s) + log4 n), where Rad(G, s) is the radius of the radio network G with respect to the source s. This result improves the previously best-known upper bound of O(Rad(G, s)+log5 n) due to Gaber and Mansour [1995]. For graphs with small genus, particularly for planar graphs, we provide an even better upper bound of Rad(G, S) + O(√Rad(G, s) · log n + log3 n) = O(Rad(G, s) + log3 n).

Original languageEnglish (US)
Article number1219954
JournalACM Transactions on Algorithms
Volume3
Issue number1
DOIs
StatePublished - Feb 1 2007

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • Radio broadcast

Fingerprint

Dive into the research topics of 'An improved algorithm for radio broadcast'. Together they form a unique fingerprint.

Cite this