An algorithm for inverse minimum spanning tree problem
- 1 January 1997
- journal article
- research article
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 8 (1) , 69-84
- https://doi.org/10.1080/10556789708805666
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 methodKeywords
This publication has 6 references indexed in Scilit:
- Inverse maximum flow and minimum cut problemsOptimization, 1997
- Calculating some inverse linear programming problemsJournal of Computational and Applied Mathematics, 1996
- A column generation method for inverse shortest path problemsMathematical Methods of Operations Research, 1995
- An inverse problem of the weighted shortest path problemJapan Journal of Industrial and Applied Mathematics, 1995
- On an instance of the inverse shortest paths problemMathematical Programming, 1992
- Graph Theory with ApplicationsPublished by Springer Nature ,1976