多参数最小支撑树问题的复杂性和算法

• 作者: 姚恩瑜 李帮义
• 来源期刊: 控制与决策
• 学科: 数学
• 关键词: 最小支撑树 NP-完全 算法
• 年，卷（期）: 2000,（5）
• 所属期刊栏目: 短文
• 页码范围: 617-619
• 分类号: O122.4
• 语种: 中文
• DOI: 10.3321/j.issn:1001-0920.2000.05.027

摘要

建立了多参数最小支撑树问题(RMST)的模型,并证明该问题是NP-完全的.利用经典Greedy算法,给出了该问题的一个近似算法,并分析了该近似算法的性能比,证明了所给出的界是紧的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姚恩瑜	浙江大学应用数学系	17	117	5.0	10.0
2	李帮义	浙江大学应用数学系	5	48	3.0	5.0