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

研究内部节点受限的最小生成树问题：给定一个赋权无向完全图[G=V,E]，假定[w:E→R]为边集[E]的权重函数且满足三角不等式，给定点集[V]的一个子集[RR?V]，目标是寻找图[G]的一个满足[R]中的点皆为内部顶点的权重最小的生成树。由于该问题是[NP-]困难的，提出了一个伪多项式时间最优算法，设计了一个近似比为2的多项式时间近似算法，并且给出例子以说明该近似比是紧的。