内部节点受限的最小生成树问题算法研究

摘要

研究内部节点受限的最小生成树问题:给定一个赋权无向完全图G=(权重函数且满足三角不等式,给定点集V的一个子集R(顶点的权重最小的生成树.由于该问题是NP-困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的.)V,E,假定w:E→R+为边集E的)R?V,目标是寻找图G的一个满足R中的点皆为内部%The minimum internal nodes constrained spanning tree problem is considered. Give a metric graph G = ( with a cost function w:E → R+ and one subset R of V (R ? V) , the minimum internal nodes constrained spanning tree problem asks for a minimum weight spanning tree such that every vertex in R is not a leaf. As the problem is NP - hard, a Pseudo-polynomial time optimal algorithm is first provided, then a simple polynomial time approximation algorithm with a performance ratio of 2 is designed and an instance is constructed to show the ratio is tight.