DEGREE-CONSTRAINED MINIMUM SPANNING TREE
DEGREE-CONSTRAINED MINIMUM SPANNING TREE
复制标题
DOI：
10.1016/0305-0548(80)90022-2
复制
发表时间：
1980-01-01
影响因子：
4.6
通讯作者：
HO, CA
中科院分区：
文献类型：
--
作者：
NARULA, SC;HO, CA
本文定义了度约束最小生成树问题。该问题被表述为线性0-1整数规划问题。提出了一个原始的和一个双重的启发式（建设）过程和分支定界算法来构建一个DCMST。这些程序都说明了一个简单的例子。一些计算经验，这些算法也报告。
In this paper the problem of a degree-constrained minimum spanning tree (DCMST) is defined. The problem is formulated as a linear 0–1 integer programming problem. A primal and a dual heuristic (construction) procedure and a branch-and-bound algorithm are proposed to construct a DCMST. These procedures are illustrated with a simple example. Some computational experience with these algorithms is also reported.