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

AN APPROXIMATION ALGORITHM OF MINIMUM SPANNING TREE WITH EDGES AND VERTICES WEIG

作　　者：李镇坚[1] 朱洪[1] 

机构地区：[1]复旦大学计算机科学与工程系,上海200433

出　　处：《计算机应用与软件》2008年第1期12-13,共2页Computer Applications and Software

基　　金：国家自然科学基金(60496321;60373021);上海市科技发展基金(03JC14014)资助

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

关 键 词：最小生成树 近似算法 近似度 NP难 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]