tree_broadcast_center

tree_broadcast_center(G)

Return the broadcast center of a tree.

The broadcast center of a graph G denotes the set of nodes having minimum broadcast time [1]. This function implements a linear algorithm for determining the broadcast center of a tree with n nodes. As a by-product, it also determines the broadcast time from the broadcast center.

Parameters:

GGraph

The graph should be an undirected tree.

Returns:

b_T, b_C(int, set) tuple

Minimum broadcast time of the broadcast center in G, set of nodes in the broadcast center.

Raises:

NetworkXNotImplemented

If G is directed or is a multigraph.

NotATree

If G is not a tree.

References

[1]

Slater, P.J., Cockayne, E.J., Hedetniemi, S.T, Information dissemination in trees. SIAM J.Comput. 10(4), 692–701 (1981)