摘要
满Steiner树问题(TST)是求解一个正则点都是叶子的最小Steiner树问题.Fabio Viduani Martinez等人给出了此问题的近似算法,它的性能比为2ρ-ρ/(3ρ-2)≈2.52,而目前求解Steiner树问题的近似算法的性能比,最小值约为1.550.对满Steiner树问题给出了一个近似算法,并将它的性能比改进为2ρ-3ρ/(6ρ-2)≈2.463.
The full Steiner tree problem（TST） is to find a minimum weight Steiner tree with all the vertices of its leaves. Fabio Viduani Martinez and other people presented a approximation algorithm, where is the approximation ratio of the algorithm for the regular graph Steiner tree problem. For now, its minimum value is approximate 1. 550. In this paper, about this full Steiner tree problem we give an approximation algorithm with an improved approximation ratio of （currently）.
出处
《菏泽学院学报》
2006年第5期1-5,共5页
Journal of Heze University
基金
国家自然科学基金资助项目(10471096)
