Faster broadcasting in unknown radio networks

We study the time of distributed deterministic broadcasting in synchronous radio networks of unknown topology and size. If a node u can be reached from two nodes which send messages in the same round, none of the messages is received by u. We assume that nodes are completely ignorant of the network: they know neither its topology, nor size, nor even their immediate neighborhood, The initial knowledge of every node is limited to its own label. Chlebus et al, [Proc, 11th Annual ACM-SIAM Symp. on Discrete Algorithms, 2000, p. 861] constructed a broadcasting algorithm working in time O(n(11/6)) under this total ignorance scenario. We improve this result by showing how to broadcast in time O(n(5/3)(log n)(1/3)) in the same model. (C) 2001 Elsevier Science B.V. All rights reserved.