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

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