摘要
给定一个网络G,欲求一个所有通路的边数不超过给定的正整数k且权最小的生成树.在此给出的近似算法是从一个可行树出发,经过改进的程序,求出其近似解——局部最优解可行树,并具体给出了一个分枝定界算法.
The constraint minimum wight spanning tree problem is studied. The heuristic algorithm which sets out from a feasible tree is proposed to seek for a tree,in which the number of links in each path is no more than a positive integer k given proviously, so that it's wight is as small as possible. A branch-bound algorithm is designed to obtain a exact solution.
出处
《烟台师范学院学报（自然科学版）》
1992年第3期1-4,共4页
Yantai Teachers University journal(Natural Science Edition)
关键词
生成树
约束极小树
分枝定界算法
spanning tree, constraint minimal tree, heuristic algorithm, branch-bound algorithm, incombent
