Broadcast Time

Consider a broadcast scheme on a connected graph from an originator vertex v in a graph G consisting of a sequence of parallel calls starting from v. 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 G rooted at v called the broadcast tree of originator v.

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

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

See also

Gossiping, Graph Bandwidth

Explore with Wolfram|Alpha


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. Du 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.

Cite this as:

Weisstein, Eric W. "Broadcast Time." From MathWorld--A Wolfram Web Resource.

Subject classifications