Constant-Length Labelling Schemes for Faster Deterministic Radio Broadcast
Faith Ellen, Seth Lewis Gilbert · 2020
In this paper, we consider the problem of broadcast from a specified source node in a known synchronous radio network. In 2019, Ellen, Gorain, Miller and Plc showed that this is possible if each node in the network only stores 2 (carefully chosen) bits of information. They proved that in an n-node network, their algorithm ensures that the broadcast completes within 2n-3 rounds. We show that storing only a small constant number of additional bits, it is possible to broadcast significantly faster when the source eccentricity, D, of the network is o(n).