10.3969/j.issn.1002-137X.2011.10.004
Steiner Tree问题的研究进展
Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用.随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT).介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展.最后,提出了该问题的进一步研究方向.
Steiner树、近似算法、精确算法、参数算法
38
TP301.6(计算技术、计算机技术)
国家自然科学基金60873265,61073036;高等学校博士学科点专项科研基金20090162110056;2009新世纪优秀人才支持计划NCET-10-0798
2012-02-21(万方平台首次上网日期,不代表论文的发表时间)
共7页
16-22