一种点边带权最小生成树的近似算法

• 作者: 朱洪 李镇坚
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 最小生成树 近似算法 近似度 NP难
• 年，卷（期）: 2008,（1）
• 所属期刊栏目: 基金项目论文
• 页码范围: 12-13
• 页数: 2页
• 分类号: TP3
• 字数: 1567字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2008.01.005

摘要

在给定的一个除边有代价外点也有两种代价的图中,要求出一棵点边代价和最小的生成树.这个优化问题具有实际应用背景.证明了该问题是NP难的,并且也给出该问题的近似算法和近似度分析.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱洪	复旦大学计算机科学与工程系	29	159	7.0	12.0
2	李镇坚	复旦大学计算机科学与工程系	2	14	2.0	2.0