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