一类最小支撑树的逆问题及其求解方法

本文针对传统的基于边的最小支撑树逆问题，提出了一类基于点边更新策略的最小支撑树逆问题．更新一个点是指减少与此点相关联的某些边的权值．根据是否含有更新点的费用，考虑了两类模型，它们均可转化为森林上的最小(费用)点覆盖的求解问题，算法的复杂性都是O(mn)，其中m=|E|n=|V|。

A Class of Inverse Minimum Spanning Tree Problems and Their Solution Methods

In this paper, corresponding to the classical edge based inverse minimum spanning tree problem, we propose a class of inverse minimum spanning tree problems under a node-edge upgrade strategy. Upgrading a node means reducing the weights on some edges incident to the node. Two models are considered according to with or without the upgrade cost of a node. Both of them can be solved efficiently by finding a minimum (weighted) node cover in a forest and complexities of the algorithms are all O(mn), where