On time-efficient broadcast in wireless networks

As broadcasting is one of the primary functions in radio networks, fast algorithms for performing it are of considerable interest. A radio network consists of stations that can act at any a given time step either as transmitters or as receivers. Given a deployment of the stations, the reception conditions can be modeled by a graph, where the existence of an edge between two nodes indicates that transmissions of one of them can reach the other, i.e., these nodes can communicate directly. The message transmitted by a node in given time step is delivered in the same time step to all of its neighbors in the graph. A node acting as a receiver in a given step will successfully receive a message if and only if exactly one of its neighbors transmits in that step. If two or more neighbors of a node transmit simultaneously, then a collision occurs and none of the messages is heard by the node in that step.