内部节点受限的最小生成树问题算法研究
来源：计算机工程与应用杂志2017年第10期北京时间：
作者：蒋小娟1，张 安1，陈 永1，陈光亭2
单位：1.杭州电子科技大学 理学院，杭州 310018；2.台州学院，浙江 台州 317000
摘要：研究内部节点受限的最小生成树问题：给定一个赋权无向完全图[G=V,E]，假定[w:E→R+]为边集[E]的权重函数且满足三角不等式，给定点集[V]的一个子集[RR?V]，目标是寻找图[G]的一个满足[R]中的点皆为内部顶点的权重最小的生成树。由于该问题是[NP-]困难的，提出了一个伪多项式时间最优算法，设计了一个近似比为2的多项式时间近似算法，并且给出例子以说明该近似比是紧的。
关键词：无向赋权图,生成树,近似算法,近似比
