Liu, Longcheng; Yao, Enyu Inverse min-max spanning tree problem under the weighted sum-type Hamming distance. (English) Zbl 1145.68038 Theor. Comput. Sci. 396, No. 1-3, 28-34 (2008). Summary: The inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. In this paper, we consider the inverse min-max spanning tree problem under the weighted sum-type Hamming distance. For the model considered, we present a combinatorial algorithm that runs in strongly polynomial times. Cited in 19 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 90C27 Combinatorial optimization 90C35 Programming involving graphs or networks Keywords:min-max spanning tree; inverse problem; Hamming distance; strongly polynomial algorithms PDFBibTeX XMLCite \textit{L. Liu} and \textit{E. Yao}, Theor. Comput. Sci. 396, No. 1--3, 28--34 (2008; Zbl 1145.68038) Full Text: DOI References: [1] Camerini, P. M., The min-max spanning tree problem and some extensions, Information Processing Letters, 7, 10-14 (1978) · Zbl 0373.05028 [2] Yang, X. G.; Zhang, J. Z., Some inverse min-max network problems under weighted \(l_1\) and \(l_\infty\) norms with bound constraints on changes, Journal of Combinatorial Optimization, 13, 123-135 (2007) · Zbl 1198.90382 [3] Heuberger, C., Inverse optimization: A survey on problems, methods, and results, Journal of Combinatorial Optimization, 8, 329-361 (2004) · Zbl 1084.90035 [4] He, Y.; Zhang, B. W.; Yao, E. Y., Weighted inverse minimum spanning tree problems under Hamming distance, Journal of Combinatorial Optimization, 9, 91-100 (2005) · Zbl 1066.90104 [5] He, Y.; Zhang, B. W.; Zhang, J. Z., Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance, Journal of Global Optimization, 34, 3, 47-474 (2006) · Zbl 1098.90062 [6] Zhang, B. W.; Zhang, J. Z.; He, Y., The center location improvement problem under the Hamming distance, Journal of Combinatorial Optimization, 9, 187-198 (2005) · Zbl 1079.90084 [7] Yang, X. G.; Zhang, J. Z., (Some New Results on Inverse Sorting Problems. Some New Results on Inverse Sorting Problems, Lecture Notes in Computer Science, vol. 3595 (2005)), 985-992 · Zbl 1128.68351 [8] Liu, L. C.; Zhang, J. Z., Inverse maximum flow problems under the weighted Hamming distance, Journal of Combinatorial Optimization, 12, 395-408 (2006) · Zbl 1126.90070 [9] Liu, L. C.; Yao, E. Y., Weighted inverse minimum cut problem under the bottleneck type Hamming distance, Asia-Pacific Journal of Operational Research, 24, 5, 725-736 (2007) · Zbl 1159.90319 [10] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs · Zbl 1201.90001 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.