THE HYBRID SPANNING TREE PROBLEM

NCU Institutional Repository > 管理學院 > 資訊管理研究所 > 期刊論文 > Item 987654321/29697

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/29697

题名:	THE HYBRID SPANNING TREE PROBLEM
作者:	CHEN,YL
贡献者:	資訊管理研究所
日期:	1994
上传时间:	2010-06-29 20:38:29 (UTC+8)
出版者:	中央大學
摘要:	The minimal spanning tree problem is a well-known problem in operations research. In this paper, a new variant of the minimal spanning tree problem, termed the hybrid spanning tree problem, is proposed. This problem assumes that each edge in the network has two attributes, where the first is the cost and the second is the degree of difficulty. The bottleneck of a tree is the maximum degree of difficulty of all edges in the tree. The hybrid spanning tree problem is to find a spanning tree in the network such that the weighted objective function of alpha x (the total cost of the tree) + beta x (the bottleneck of the tree) is minimized. In this paper, two efficient algorithms are proposed. When the values of alpha and beta are given nonnegative constants, the first algorithm can find the minimal weight spanning tree in time of O(mn), where m and n are the numbers of edges and nodes in the network, respectively. When the values of alpha and beta are nonnegative variables, the second algorithm can find all possible minimal weight spanning trees also in time O(mn).
關聯:	EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
显示于类别:	[資訊管理研究所] 期刊論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	643	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing