| 一种点边带权最小生成树的近似算法 |
| |
| 引用本文： | 李镇坚,朱洪. 一种点边带权最小生成树的近似算法[J]. 计算机应用与软件, 2008, 25(1): 12-13 |
| |
| 作者姓名： | 李镇坚 朱洪 |
| |
| 作者单位： | 复旦大学计算机科学与工程系,上海,200433;复旦大学计算机科学与工程系,上海,200433 |
| |
| 基金项目： | 本研究受到国家自然科学基金（60496321,60373021）以及上海市科技发展基金（03JC14014）资助. |
| |
| 摘 要： | 在给定的一个除边有代价外点也有两种代价的图中，要求出一棵点边代价和最小的生成树。这个优化问题具有实际应用背景。证明了该问题是NP难的，并且也给出该问题的近似算法和近似度分析。
|
| 关 键 词： | 最小生成树 近似算法 近似度 NP难 |
| 收稿时间： | 2006-04-13 |
| 修稿时间： | 2006-04-13 |
AN APPROXIMATION ALGORITHM OF MINIMUM SPANNING TREE WITH EDGES AND VERTICES WEIG |
| |
| Li Zhenjian,Zhu Hong. AN APPROXIMATION ALGORITHM OF MINIMUM SPANNING TREE WITH EDGES AND VERTICES WEIG[J]. Computer Applications and Software, 2008, 25(1): 12-13 |
| |
| Authors: | Li Zhenjian Zhu Hong |
| |
| Affiliation: | HTLi Zhenjian Zhu Hong(Department of Computer Science , Engineering,Fudan University,Shanghai 200433,China) |
| |
| Abstract: | With a graph in which vertices have two kinds of cost besides edges cost, a minimum spanning tree with edges and vertices weight is found. The optimization problem has practical application. It is proved that the problem is NP-hard. The approximation algorithm for the optimization problem and the analysis of the approximation ratio are presented. |
| |
| Keywords: | Minimum spanning tree Approximation algorithm Approximation ratio NP-hard |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
