tree_broadcast_time#

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

Return the minimum broadcast time of a (node in a) tree.

The minimum broadcast time of a node is defined as the minimum amount of time required to complete broadcasting starting from that node. 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.

Parameters:
GGraph

The graph should be an undirected tree.

nodenode, optional (default=None)

Starting node for the broadcasting. If None, the algorithm returns the broadcast time of the graph instead.

Returns:
int

Minimum broadcast time of node in G, or broadcast time of G if no node is provided.

Raises:
NetworkXNotImplemented

If G is directed or is a multigraph.

NodeNotFound

If node is not a node in G.

NotATree

If G is not a tree.

References

[1]

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.