Improved schedule for radio broadcast
Michael Elkin, Guy Kortsarz · Symposium on Discrete Algorithms · 2005
We show that for every radio network G = (V, E) and source s e V, there exists a radio broadcast schedule for G of length Rad(G, s) + O(√ Rad(G, s). log2n) = O(Rad(G, s) + log4n), 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)+log5n) due to Gaber and Mansour [12].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 + log3n) = O(Rad(G, s) + log3n).