Steiner Tree问题的研究进展

被引：9

作者：

郑莹

王建新

陈建二

机构：

[1] 中南大学信息科学与工程学院

来源：

计算机科学 | 2011年 / 38卷 / 10期

基金：

高等学校博士学科点专项科研基金;

关键词：

Steiner树; 近似算法; 精确算法; 参数算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

收藏

页码：16 / 22

页数：7

相关论文

共 13 条

[1] Speeding up the Dreyfus–Wagner algorithm for minimum Steiner trees [J].

Bernhard Fuchs ;

Walter Kern ;

Xinhui Wang .

Mathematical Methods of Operations Research, 2007, 66 :117-125

[2] A polylogarithmic approximation algorithm for the group Steiner tree problem [J].

Garg, N ;

Konjevod, G ;

Ravi, R .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2000, 37 (01) :66-84

[3] Two heuristics for the Euclidean Steiner tree problem [J].

Dreyer, DR ;

Overton, ML .

JOURNAL OF GLOBAL OPTIMIZATION, 1998, 13 (01) :95-106

[4] A series of approximation algorithms for the acyclic directed Steiner tree problem [J].

Zelikovsky, A .

ALGORITHMICA, 1997, 18 (01) :99-110

[5] New approximation algorithms for the Steiner tree problems [J].

Karpinski, M ;

Zelikovsky, A .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 1997, 1 (01) :47-65

[6] A NEARLY BEST-POSSIBLE APPROXIMATION ALGORITHM FOR NODE-WEIGHTED STEINER TREES [J].

KLEIN, P ;

RAVI, R .

JOURNAL OF ALGORITHMS, 1995, 19 (01) :104-115

[7] AN 11-6-APPROXIMATION ALGORITHM FOR THE NETWORK STEINER PROBLEM [J].

ZELIKOVSKY, AZ .

ALGORITHMICA, 1993, 9 (05) :463-470

[8]

A proof of the Gilbert-Pollak conjecture on the Steiner ratio[J] . D. -Z. Du,F. K. Hwang.Algorithmica . 1992 (1)

[9] A DUAL ASCENT APPROACH FOR STEINER TREE PROBLEMS ON A DIRECTED GRAPH [J].

WONG, RT .

MATHEMATICAL PROGRAMMING, 1984, 28 (03) :271-287

[10] A FAST ALGORITHM FOR STEINER TREES [J].

KOU, L ;

MARKOWSKY, G ;

BERMAN, L .

ACTA INFORMATICA, 1981, 15 (02) :141-145