1997•Optimization methods & softwareRequires access
An algorithm for inverse minimum spanning tree problem
Jianzhong Zhang, Shaoji Xu, Zhongfan Ma
Open publisher page 43 citations
Abstract
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