Broadcast Time

Consider a broadcast scheme on a connected graph from an originator vertex  in a graph  consisting of a sequence of parallel calls starting from . In each time step, every informed node (sender) can call at most one uninformed neighbor (receiver), corresponding to a directed edge. The process is iterated until every vertex in the network is informed, with the result being a directed spanning tree of  rooted at  called the broadcast tree of originator .

The minimum number of time steps required to broadcast from  to all vertices in the graph  is called the broadcast time of vertex , denoted . The maximum broadcast time over all originator vertices in  is called the broadcast time of , denoted  (Harutyunyan1 and Li 2019).

The broadcast time of a disconnected graph is the maximum of the broadcast times of its connected components.

REFERENCES

Farley, A. M. "Minimal Broadcast Networks." Networks 9, 313-332, 1979.

Harutyunyan, H. A. and Li, Z. "A Simple Construction of Broadcast Graphs." In Computing and Combinatorics. COCOON 2019 (Ed. D. Z.and C. Tian.) Cham, Switzerland: Springer, pp. 240-253, 2019.

Ivanova, M.; Haugland, D.; and Tvedt, B. H. "Computing the Broadcast Time of a Graph." 13 Jul 2021. https://arxiv.org/abs/2107.06359v1.