Abstract: The minimum internal nodes constrained spanning tree problem is considered. Give a metric graph [G=V,E] 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.

Key words: undirected weighted graph, spanning tree, approximation algorithm, performance ratio

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

关键词: 无向赋权图, 生成树, 近似算法, 近似比