On a Condition for Obtaining an Explicit Solution of Optimum Requirement Spanning Tree

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