An inverse model for the least uniform spanning tree problems

In this paper, we consider an inverse model for the least uniform spanning tree (ILUS) problems. Let T be a spanning tree of a network G. Define the degree of balance of T as the difference between the maximum and the minimum weight of the edges in T. (ILUS) problem can be described as: how to change the weight vector w of G under a given budget constraint so that the maximum degree of balance of the spanning trees of G is minimized. After discussing some characteristics of (ILUS) problem, we show that this problem can be solved efficiently by strongly polynomial algorithm.