tree_broadcast_time(G, node=None)[source]#

Return the Broadcast Time of the tree G.

The minimum broadcast time of a node is defined as the minimum amount of time required to complete broadcasting starting from the originator. The broadcast time of a graph is the maximum over all nodes of the minimum broadcast time from that node [1]. This function returns the minimum broadcast time of node. If node is None the broadcast time for the graph is returned.

Gundirected graph

The graph should be an undirected tree

node: int, optional

index of starting node. If None, the algorithm returns the broadcast time of the tree.


Broadcast Time of a node in a tree


If the graph is directed or is a multigraph.



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.) Springer, pp. 240-253, 2019.