Fast broadcasting and gossiping in radio networks

We establish an O(n log(2) n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Q (n log n). The fastest previously known algorithm for this problem works in time O (n(3/2)). Using our broadcasting 'algorithm, we develop an O (n(3/2) log(2) n) algorithm for gossiping in the same network model. (C) 2002 Elsevier Science (USA). All rights reserved.