Premium
On a condition for obtaining an explicit solution of optimum requirement spanning tree
Author(s) -
Anazawa Tsutomu
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199909)34:2<132::aid-net6>3.0.co;2-l
Subject(s) - spanning tree , minimum spanning tree , combinatorics , tree (set theory) , minimum degree spanning tree , mathematics , degree (music) , distributed minimum spanning tree , kruskal's algorithm , mathematical optimization , computer science , physics , acoustics
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. © 1999 John Wiley & Sons, Inc. Networks 34: 132–135, 1999