AuthorsF. Manne and Q. Xin
TitleTime Efficient Radio Broadcasting in Planar Graphs
Publication TypeJournal Article
Year of Publication2008
JournalJournal of Networks
Date PublishedFebruary

We study the communication primitive of broadcasting (one-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology of the network. We show that radio broadcasting can be completed in D+O(łog n) time units in planar graphs of size n, and with diameter D. This improves the currently best known D+O(łog^3n) time schedule proposed by Elkin and Kortsarz in \cite{EK05} [SODA'05], and 3D time schedule due to Gąsieniec, Peleg and Xin in \cite{GPX05} [PODC'05]. In this paper, we also explore broadcasting in radio networks in the presence of edge failures.

Citation KeySimula.ND.76