哈明距离下极大不一致支撑树的部分逆问题  

The partial inverse least uniform spanning tree problem under hamming distance

作　　者：于倩[1] 王勤[1] 白艳琴[1] 

机构地区：[1]中国计量学院理学院,浙江杭州310018

出　　处：《中国计量学院学报》2010年第3期271-273,共3页Journal of China Jiliang University

基　　金：国家自然科学基金资助项目(No.10601051);浙江省自然科学基金资助项目(No.Y6090472)

摘　　要：给定一个简单无向赋权图和其中的一个森林,极大不一致支撑树的部分逆问题研究如何尽可能少地改变图中各边的权,使得在新的权值下存在一个极大不一致支撑树包含该森林.在赋权哈明距离下,得到了该问题的一些性质,并且给出了求解该问题的多项式时间算法.The objective of a partial inverse optimization problem was to find a minimum perturbation of the parameter values,in an underlying optimization problem with a partially given solution,such that the partial solution become a part of the optimal solution under the new parameters.Given a simple undirected weighted graph and a forest,the partial inverse least uniform spanning tree problem was how to adjust the weights of the edges as small as possible so that the partially given forest is contained in a new le...

关 键 词：部分逆问题 极大不一致支撑树 哈明距离 多项式时间算法 

分 类 号：O157.5[理学—数学]