Abstract
In this paper, we consider the inverse minimum spanning tree problem under the bottleneck-type Hamming distance, where the weights of edges can be modified only within given intervals. We further consider the constrained case in which the total modification cost cannot exceed a given upper bound. It is shown that these inverse problems can be transformed into a minimum node cover problem on a bipartite graph, and we give a strongly polynomial time algorithm to solve this type of node cover problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Y. He B. Zhang E. Yao (2005) ArticleTitleWeighted inverse minimum spanning tree problems under Hamming distance Journal of Combinatorial Optimization. 9 91–100 Occurrence Handle10.1007/s10878-005-5486-1
C. Heuberger (2004) ArticleTitleInverse optimization: A survey on problems, methods, and results Journal of Combinatorial Optimization 8 329–361 Occurrence Handle10.1023/B:JOCO.0000038914.26975.9b
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by The National Natural Science Foundation of China (60021201), The Hong Kong Research Grant Council under the grant CERG 9040883 (CITYU 103003), and the Doctoral Foundation of Hohai University (2005-02).
Rights and permissions
About this article
Cite this article
Zhang, B., Zhang, J. & He, Y. Constrained Inverse Minimum Spanning Tree Problems under the Bottleneck-Type Hamming Distance. J Glob Optim 34, 467–474 (2006). https://doi.org/10.1007/s10898-005-6470-0
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10898-005-6470-0