On the Minimal Total Path Length of a Spanning Tree
Andy N. C. Kang, David A. Ault · Computer Science Technical Reports (Virginia Tech) · 1974
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.