On the Minimal Total Path Length of a Spanning Tree
Kang, Andy N. C.
Ault, David A.
MetadataShow full item record
The notions of a balance node and the total path length with respect to a node u of a spanning tree are defined. We show that the total path length of a spanning tree with respect to u is minimal if and only if u is a balance node. An algorithm is also given to locate a balance node. A proof of the correctness of the algorithm is given and the complexity of the algorithm is analyzed.