On the inverse minimum spanning tree problem with minimum number of perturbed edges

Abstract

Let G=〈V, E, L〉 be a network with the vertex set V, the edge set E and the length vector L, and let T* be a prior determined spanning tree of G. The inverse minimum spanning tree problem with minimum number of perturbed edges is to perturb the length vector L to L+δ, such that T* is one of minimum spanning trees under the length vector L+δ and the number of perturbed edges is minimum. This paper establishes a mathematical model for this problem and transforms it into a minimum vertex covering problem in a bipartite graph G ₀, a path-graph. Thus a strongly polynomial algorithm with time complexity O(mn ²) can be designed by using Hungarian method.

Keywords

Inverse network optimization problem / minimum spanning tree / vertex covering set

References

[1] Bondy J.A., Murty P.. Graph Theory with Applications, 1978, London: The Macmillan Press, LTD.

[2] Burton D., Toint P.L.. On the instance of the inverse shortest paths problem. Math Program, 1992, 53: 45-61.

[3] Burton D., Toint P.L.. On the use of an inverse shortest paths algorithm for recovering linearly correlated cost. Math Program, 1994, 63: 1-22.

[4] Huang S., Liu Z.H.. On the inverse problem of linear programming and its applications to minimum weigh perfect k-matching in bipartite graph. European Journal of Operational Research, 1999, 112: 421-426.

[5] Sokkaling P.T.. The minimum cost flow problems: Primal algorithm and cost perturbations, 1995, India: Department of Mathematics, Indian Institute of Technology

[6] Sokkalingam P.T., Ahuja R.K., Orlin J.B.. Solving inverse spanning tree problems through network flow techniques. Operation Research, 1999, 47: 291-298.

[7] Xu S., Zhang J.. An inverse problem of the weighted shortest path problems. Japanese J. Appl and Industrial Math, 1995, 12: 47-59.

[8] Yang C., Zhang J.. Inverse maximum capacity problems. OR Spektrum, 1998, 20: 97-100.

[9] Zhang J., Liu Z.H., Ma. Z.F.. On the inverse problem of minimum spanning tree with partition constraints. Mathematical Methods of Operations Research, 1996, 44: 171-187.