Abstract
In this paper, we consider weighted inverse minimum spanning tree problems under Hamming distance. Three models are considered: unbounded case, unbounded case with forbidden edges, and general bounded case. In terms of the method for minimum-weight node cover problem on bipartite graph, we present their respective strongly polynomial algorithms.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R.K. Ahuja, T.L. Magnanti, and J.B. Orlin Network Flows: Theory, Algorithms, and Applications, Prentice Hall: Englewood Cliffs, NJ, 1993.
R.K. Ahuja and J.B. Orlin “A faster algorithm for the inverse spanning tree problem,”Journal of Algorithms, vol. 34, pp. 177–193, 2000.
C. Heuberger “Inverse optimization: A survey on problems, methods, and results,”Journal of Combinatorial Optimization, vol. 8, pp. 329–361, 2004.
E.L. Lawler Combinatorial Optimization: Networks and Matroids, Holt, Rinehart & Winston, 1976.
B.Y. Li “New models for spanning tree problems in network optimization: Algorithms and complexity,”Ph.D. Thesis, Zhejiang University, Hangzhou, 2000.
R. Motwani Approximation Algorithms, Lecture Notes, Stanford University, Stanford, 2000.
P.T. Sokkalingam, R.K. Ahuja, and J.B. Orlin “Solving inverse spanning tree problems through network flow techniques,”Oper. Res., vol. 47, pp. 291–298, 1999.
J. Zhang and Z. Liu “A generalized model of some inverse combinatorial optimization problems and its solution method under l∞ norm,”Journal of Combinatorial Optimization, vol. 6, pp. 207–227, 2002.
J. Zhang, Z. Liu, and Z. Ma “On the inverse problem of minimum spanning tree with partition constraints,”Math. Methods Oper. Res., vol. 44, pp. 171–188, 1996.
J. Zhang and Z. Ma “Solution structrue of some inverse combinatorial optimization problems,”Journal of Combinatorial Optimization, vol. 3, pp. 127–139, 1999.
J. Zhang, S. Xu, and Z. Ma “An algorithm for inverse minimum spannimg tree problem,”Optimization Metheds & Software, vol. 8, pp. 69–84, 1997.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported by TRAPOYT, National Natural Science Foundation of China (10271110, 60021201)
Rights and permissions
About this article
Cite this article
He, Y., Zhang, B. & Yao, E. Weighted Inverse Minimum Spanning Tree Problems Under Hamming Distance. J Comb Optim 9, 91–100 (2005). https://doi.org/10.1007/s10878-005-5486-1
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10878-005-5486-1