TY - JOUR

T1 - The hybrid spanning tree problem

AU - Chen, Y. L.

PY - 1994/8/25

Y1 - 1994/8/25

N2 - 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 α × (the total cost of the tree) + β × (the bottleneck of the tree) is minimized. In this paper, two efficient algorithms are proposed. When the values of α and β 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 α and β are nonnegative variables, the second algorithm can find all possible minimal weight spanning trees also in time O(mn).

AB - 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 α × (the total cost of the tree) + β × (the bottleneck of the tree) is minimized. In this paper, two efficient algorithms are proposed. When the values of α and β 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 α and β are nonnegative variables, the second algorithm can find all possible minimal weight spanning trees also in time O(mn).

KW - combinatorial analysis

KW - computational analysis

KW - graphs

KW - minimal spanning tree

KW - Network

UR - http://www.scopus.com/inward/record.url?scp=0028485129&partnerID=8YFLogxK

U2 - 10.1016/0377-2217(94)90037-X

DO - 10.1016/0377-2217(94)90037-X

M3 - 期刊論文

AN - SCOPUS:0028485129

SN - 0377-2217

VL - 77

SP - 179

EP - 188

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 1

ER -