An inverse model for the least uniform spanning tree problems

摘要：

In this paper, we consider an inverse model for the least uniform spanning tree (ILUS) problems. Let T be a spanning tree of a network G. Define the degree of balance of T as the difference between the maximum and the minimum weight of the edges in T. (ILUS) problem can be described as: how to change the weight vector w of G under a given budget constraint so that the maximum degree of balance of the spanning trees of G is minimized. After discussing some characteristics of (ILUS) problem, we show that this problem can be solved efficiently by strongly polynomial algorithm.

关键词： Inverse optimization Least uniform spanning tree Computational complezity Strongly polynomial algorithm

作者: Wu Long-Shu Wang Qin Qiao Cheng

作者单位: College of Science China Jiliang UniversityHangzhou 310018, China Department of Mathematics China Jiliang University Hangzhou 310018, China

会议类型: 国际会议

会议名称: 第四届国际计算机新科技与教育学术会议(2009 4th International Conference on Computer Science & Education)

会议地点: 南京

会议语种:英文

页码: 1949-1952

在线出版日期: 2009-07-25（万方平台首次上网日期，不代表论文的发表时间）