Weighted Inverse Minimum Spanning Tree Problems Under Hamming Distance

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.