计算机科学与探索2011，Vol.38Issue(10)：16-22,7.
Steiner Tree问题的研究进展
Survey of Steiner Tree Problem
摘要
Abstract
Steiner tree problems are classical NP problems,which have wide applications in many fields,such as computer network arrangement,circuit design, biological network analysis and so oa With the development of parameterized computation theory, parameterized Steiner tree problem has been proved fixed parameter solvable not only in undirected graph but also in directed case This paper firstly introduced the approximation algorithms and parameterized algorithms for Steiner tree problem in general graphs,then analysed the research situation for some special Steiner tree problems. Moreover, the vertex-weighted Steiner tree problem was also discussed. Finally,some further research directions on this problem were proposed.关键词
Steiner树/近似算法/精确算法/参数算法Key words
Steiner tree, Approximation algorithm, Exact algorithm, Parameterized algorithm分类
信息技术与安全科学引用本文复制引用
郑莹,王建新,陈建二..Steiner Tree问题的研究进展[J].计算机科学与探索,2011,38(10):16-22,7.基金项目
本文受国家自然科学基金(60873265,61073036),高等学校博士学科点专项科研基金(20090162110056),2009新世纪优秀人才支持计划(NCET-10-0798)资助. （60873265,61073036）
