Steiner Tree问题的研究进展

Steiner树问题是经典的NP难解问题，在计算机网络布局、电路设计以及生物网络等领域都有很多应用。随着参数计算理论的发展，已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT)。介绍了无向图和有向图中Steiner树问题的近似算法和参数算法，分析了一些特殊Steiner树问题的研究现状，还讨论了顶点加权Steiner树问题的研究进展。最后，提出了该问题的进一步研究方向。

Survey of Steiner Tree Problem

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.