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

编号 zgly0000344249

文献类型 期刊论文

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

作者 关秀翠 

作者单位 香港城市大学数学系 

母体文献 运筹学学报 

年卷期 2004,8(4)

页码 39-44

年份 2004 

分类号 O157.5 

关键词 支撑树  逆问题  求解方法  关联  算法  覆盖  复杂性  费用  森林  权值 

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