Broadcast in radio networks
We show that for any radio network there exists a schedule of a broadcast whose time is O(D + 1og5(n)), where D is the diameter and n is the number of nodes. (This result implies an optimal broadcast to networks with D = R(log5 n).) We present a (centralized) polynomial time algorithm that given a network and a source, outputs a schedule for broadcasting the message from the source to the rest of the network.