%0 Journal Article
%T Survey of Steiner Tree Problem<br>Steiner Tree问题的研究进展
%A ZHENG Ying
%A WANG Jian-xin
%A CHEN Jian-er
%A <br>郑莹
%A 王建新
%A 陈建二
%J 计算机科学
%D 2011
%I 
%X Steiner tree problems are classical NP problems, which have wide applications in many fields, such as computo network arrangement, circuit design, biological network analysis and so on. 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 Stciner tree problems.Moreover, the vertex-weighted Steiner tree problem was also discussed. Finally, some further research directions on this problem were proposed.
%K Steiner tree
%K Approximation algorithm
%K Exact algorithm
%K Parameterized algorithm<br>Steiner树，近似算法，精确算法，参数算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=2AC66EB828B1E435C4C3AED86E3ED9AB&yid=9377ED8094509821&vid=16D8618C6164A3ED&iid=F3090AE9B60B7ED1&sid=7801E6FC5AE9020C&eid=BC12EA701C895178&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=0