An improved algorithm for radio broadcast
Michael Elkin, Guy Kortsarz · ACM Transactions on Algorithms · 2007
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 ) ⋅log 2 n ) = O ( Rad ( G , s ) + log 4 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 ) + log 5 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 + log 3 n ) = O ( Rad ( G , s ) + log 3 n ).