Steiner Tree问题的研究进展

• 作者: 王建新 郑莹 陈建二
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: Steiner树 近似算法 精确算法 参数算法
• 年，卷（期）: 2011,（10）
• 页码范围: 16-22
• 分类号: TP301.6
• 字数: 8649字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王建新	中南大学信息科学与工程学院	371	3185	23.0	39.0
2	陈建二	中南大学信息科学与工程学院	167	1535	20.0	30.0
3	郑莹	中南大学信息科学与工程学院	4	24	2.0	4.0