内部节点受限的最小生成树问题算法研究

• 作者: 张安 蒋小娟 陈光亭 陈永
• 来源期刊: 计算机工程与应用
• 学科: 数学
• 关键词: 无向赋权图 生成树 近似算法 近似比
• 年，卷（期）: 2017,（10）
• 页码范围: 35-37
• 页数: 3页
• 分类号: O224
• 字数: 2907字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1511-0349

摘要

研究内部节点受限的最小生成树问题:给定一个赋权无向完全图G=(权重函数且满足三角不等式,给定点集V的一个子集R(顶点的权重最小的生成树.由于该问题是NP-困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的.)V,E,假定w:E→R+为边集E的)R?V,目标是寻找图G的一个满足R中的点皆为内部

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张安	杭州电子科技大学理学院	24	15	2.0	2.0
2	陈永	杭州电子科技大学理学院	22	14	2.0	2.0
3	陈光亭		10	7	2.0	2.0
4	蒋小娟	杭州电子科技大学理学院	1	2	1.0	1.0