摘要
在给定的一个除边有代价外点也有两种代价的图中,要求出一棵点边代价和最小的生成树。这个优化问题具有实际应用背景。证明了该问题是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.
出处
《计算机应用与软件》
CSCD
北大核心
2008年第1期12-13,共2页
Computer Applications and Software
基金
国家自然科学基金(60496321
60373021)
上海市科技发展基金(03JC14014)资助
关键词
最小生成树
近似算法
近似度
NP难
Minimum spanning tree Approximation algorithm Approximation ratio NP-hard
