On the Minimal Total Path Length of a Spanning Tree
| Autor: | Kang, Andy N. C., Ault, David A. |
|---|---|
| Přispěvatelé: | Computer Science |
| Jazyk: | angličtina |
| Rok vydání: | 1974 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|