An algorithm for inverse minimum spanning tree problem
Jianzhong Zhang, Shaoji Xu, Zhongfan Ma · Optimization methods & software · 1997
In this paper we consider an inverse minimum spanning tree problem in which we wish to change the original weights of the edges in a graph as little as possible so that a given spanning tree of the graph can become the minimum spanning tree. An algorithm is proposed which can solve the problem in polynomial time. The algorithm is a combinatorial method that uses the minimum covering problem as its main subproblem. An example is included to illustrate the method