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.
Keywords minimum spanning tree - inverse problem - strongly polynomial algorithm
This research is supported by TRAPOYT, National Natural Science Foundation of China (10271110, 60021201)