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
. Ifnode
isNone
, 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
inG
, or broadcast time ofG
if no node is provided.
- Raises:
- NetworkXNotImplemented
If
G
is directed or is a multigraph.- NodeNotFound
If
node
is not a node inG
.- 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.