| Article ID: | iaor20002349 |
| Country: | United States |
| Volume: | 8 |
| Issue: | 1 |
| Start Page Number: | 69 |
| End Page Number: | 84 |
| Publication Date: | Jul 1997 |
| Journal: | Optimization Methods & Software |
| Authors: | Zhang J.H., Xu S.J., Ma Z.F. |
| Keywords: | minimum spanning trees |
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.