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

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