Lexicographically Optimum Traffic Trees with Maximum Degree Constraints

Abstract

We shall consider a problem of finding an ‘optimum’ tree which is closely related to the network flow problem proposed by Ford and Fulkerson, and call the solution to this problem a lexicographically optimum traffic tree (LOTT). Before examining this problem in detail, we shall review the problem of finding an optimum requirement spanning tree (ORST) studied by Hu, which is also related to the network flow problem. We can regard the LOTT problem as a min-max problem and the ORST problem as a min-sum problem. It shall be shown that, while LOTTs and ORSTs coincide completely without maximum degree constraints, they do not always coincide with the constraints. Further, we shall show that LOTTs can be expressed by simple recursion in a special case.