An Improved Algorithm for the Most Balanced Spanning Tree Problems with Restriction on Edges

摘要：

In this paper, we consider the most balanced spanning tree problems with restriction on edges. For a given simple connected weighted graph G=(F, E, w) and a given forest F in G, where w denotes the weight vector defined on E, the problem asks to find a spanning tree T of G containing F such that the maximum difference between the weights of edges in t is as small as possible. The problem has some applications. And we show that this problem can be solved in O(|E||V|)time.

关键词： most balanced optimization spanning tree computational complezity polynomial time algorithm

作者: Longshu Wu Yanqin Bai Feilong Cao

作者单位: College of Science, China Jiliang University, Zhejiang 310018, P.R. China

会议类型: 国际会议

会议名称: The First World Congress on Global Optimization in Engineering & Science(第一届工程与科学全局优化国际会议 WCGO2009)

会议地点: 长沙

会议语种:英文

页码: 901-904

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