✦ LIBER ✦
On a condition for obtaining an explicit solution of optimum requirement spanning tree
✍ Scribed by Anazawa, Tsutomu
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 70 KB
- Volume
- 34
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
The optimum requirement spanning tree (ORST) studied by Hu is known to be obtained by the Gomory-Hu algorithm when the degrees of vertices are not restricted. We consider a problem to find an ORST with maximum-degree constraints and suggest a particular spanning tree T* as a candidate for the solution to the problem. Further, we show a condition under which the tree T* is an explicit solution to the problem.