共 1 条
[1]
On the shortest spanning subtree of a graph and the traveling salesman problem[J] . Joseph B. Kruskal.proc . 1956 (1)
约束最小支撑树(C-MST)问题:复杂性和上下界估计
被引：1
作者：
李帮义
姚恩瑜
机构：
[1] 浙江大学数学系!浙江杭州
来源：
关键词：
约束最小支撑树;
NP-完全的;
字典序最小树;
算法;
D O I：
暂无
中图分类号：
O157.5 [图论];
学科分类号：
070104 ;
摘要：
本文首先建立了约束最小支撑树问题的模型 ,利用背包问题的复杂性 ,证明了该问题是 NP-完全的 .然后利用一个广义线性规划的对偶算法 ,对目标函数的上下界作出了估计 ,最后分析了解的平面性质
引用
收藏
页码：237 / 242
页数：6
相关论文