| 关于满Steiner树问题的一个近似算法 |
| |
| 引用本文： | 罗美菊,赵传立,唐恒永.关于满Steiner树问题的一个近似算法[J].菏泽学院学报,2006,28(5):1-5. |
| |
| 作者姓名： | 罗美菊 赵传立 唐恒永 |
| |
| 作者单位： | 沈阳师范大学数学与系统科学学院,辽宁沈阳,110034 |
| |
| 摘 要： | 满Steiner树问题(TST)是求解一个正则点都是叶子的最小Steiner树问题.Fabio Viduani Martinez等人给出了此问题的近似算法,它的性能比为2ρ-ρ/(3ρ-2)≈2.52,而目前求解Steiner树问题的近似算法的性能比,最小值约为1.550.对满Steiner树问题给出了一个近似算法,并将它的性能比改进为2ρ-3ρ/(6ρ-2)≈2.463.
|
| 关 键 词： | 满Steiner树 近似算法 最小Steiner树 |
| 文章编号： | 1673-2103（2006）05-0001-05 |
| 收稿时间： | 2006-07-25 |
| 修稿时间： | 2006年7月25日 |
An Approximation Algorithm about Full Steiner Tree Problem |
| |
| LUO Mei-ju,ZHAO Chuan-li,TANG Heng-yong.An Approximation Algorithm about Full Steiner Tree Problem[J].Journal of Heze University,2006,28(5):1-5. |
| |
| Authors: | LUO Mei-ju ZHAO Chuan-li TANG Heng-yong |
| |
| Institution: | Department of Mathematics, Shenyang Normal University, Shenyang, Liaoning 110034, China |
| |
| Abstract: | 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). |
| |
| Keywords: | full Steiner tree approximation algorithm minimum Steiner tree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
