Survey of Steiner Tree Problem
Steiner Tree问题的研究进展

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.