A FASTER APPROXIMATION ALGORITHM FOR THE STEINER TREE PROBLEM IN GRAPHS

被引：30
|
作者：
ZELIKOVSKY, AZ [1 ]
机构：
[1] MAX PLANCK INST INFORMAT,SAARBRUCKEN,GERMANY
来源：
INFORMATION PROCESSING LETTERS | 1993年 / 46卷 / 02期
关键词：
COMBINATORIAL PROBLEMS; APPROXIMATION ALGORITHMS; STEINER TREE;
D O I：
10.1016/0020-0190(93)90201-J
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The Steiner tree problem requires a shortest tree spanning a given vertex subset S within graph G = (V, E). Two heuristics finding approximate Steiner trees no longer than 11/6 times of the optimal length appeared recently. They run in time O(alpha + VS2 + S4) and O(alpha + VS2 + S3.5), respectively, where alpha is the time complexity of the all-pairs-shortest-paths problem. We reduce the runtime of the first heuristic to O(S(E + VS + V log V)).
引用
收藏
页码：79 / 83
页数：5
相关论文
共 50 条
  • [1] A FASTER APPROXIMATION ALGORITHM FOR THE STEINER PROBLEM IN GRAPHS
    WU, YF
    WIDMAYER, P
    WONG, CK
    ACTA INFORMATICA, 1986, 23 (02) : 223 - 229
  • [2] A FASTER APPROXIMATION ALGORITHM FOR THE STEINER PROBLEM IN GRAPHS
    MEHLHORN, K
    INFORMATION PROCESSING LETTERS, 1988, 27 (03) : 125 - 128
  • [3] A NOTE ON A FASTER APPROXIMATION ALGORITHM FOR THE STEINER PROBLEM IN GRAPHS
    FLOREN, R
    INFORMATION PROCESSING LETTERS, 1991, 38 (04) : 177 - 178
  • [4] FasterDSP: A faster approximation algorithm for directed Steiner tree problem
    Hsieh, Ming-I
    Wu, Eric Hsiao-Kuang
    Tsai, Meng-Feng
    JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 2006, 22 (06) : 1409 - 1425
  • [5] AN EFFICIENT APPROXIMATION ALGORITHM FOR THE STEINER TREE PROBLEM IN RECTILINEAR GRAPHS
    SAKAI, K
    TSUJI, K
    MATSUMOTO, T
    1989 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS, VOLS 1-3, 1989, : 339 - 342
  • [6] A faster algorithm for the Steiner tree problem
    Mölle, D
    Richter, S
    Rossmanith, P
    STACS 2006, PROCEEDINGS, 2006, 3884 : 561 - 570
  • [7] Approximation hardness of the Steiner tree problem on graphs
    Chlebík, M
    Chlebíkov, J
    ALGORITHM THEORY - SWAT 2002, 2002, 2368 : 170 - 179
  • [8] Faster Approximation Algorithms for the Rectilinear Steiner Tree Problem
    U. Fößmeier
    M. Kaufmann
    A. Zelikovsky
    Discrete & Computational Geometry, 1997, 18 : 93 - 109
  • [9] Faster approximation algorithms for the rectilinear Steiner tree problem
    Fossmeier, U
    Kaufmann, M
    Zelikovsky, A
    DISCRETE & COMPUTATIONAL GEOMETRY, 1997, 18 (01) : 93 - 109
  • [10] A 1.598 approximation algorithm for the Steiner problem in graphs
    Hougardy, S
    Prömel, HJ
    PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1999, : 448 - 453
12345