Approximations for a bottleneck Steiner tree problem

被引:23
作者
Wang, L [1 ]
Du, DZ
机构
[1] City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China
[2] Univ Minnesota, Dept Comp Sci & Engn, Minneapolis, MN 55455 USA
关键词
Steiner tree; wireless communication;
D O I
10.1007/s00453-001-0089-4
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
In the design of wireless communication networks. due to a budget limit, suppose we could put totally n + k stations in the plane, However, n of them must be located at given point, Of course, one would like to have the distance between stations as small as possible, The problem is how to choose locations fur other k stations to minimize the longest distance between stations. This problem is NP-hard. We show that if NP not equal P, no polynomial-time approximation for the problem in the rectilinear plane has a performance ratio less than 2 and no polynomial-time approximation for the problem in the Euclidean plane has a performance ratio less than root2 and that there exists a polynomial-time approximation with performance ratio 2 for the problem in both the rectilinear plane and the Euclidean plane.
引用
收藏
页码:554 / 561
页数:8
相关论文
共 22 条
  • [1] AboElFotoh HMF, 1997, NETWORKS, V29, P117, DOI 10.1002/(SICI)1097-0037(199703)29:2<117::AID-NET6>3.0.CO
  • [2] 2-M
  • [3] ARORA S, 1996, P 37 FOCS
  • [4] CHANG C, 1990, IEEE T COMPUT AID D, V19, P1318
  • [5] CHEN D, UNPUB APPR STEINER T
  • [6] DU DZ, 1992, ALGORITHMICA, V7, P121, DOI 10.1007/BF01758755
  • [7] Optimal and approximate bottleneck Steiner trees
    Ganley, JL
    Salowe, JS
    [J]. OPERATIONS RESEARCH LETTERS, 1996, 19 (05) : 217 - 224
  • [8] COMPLEXITY OF COMPUTING STEINER MINIMAL TREES
    GAREY, MR
    GRAHAM, RL
    JOHNSON, DS
    [J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) : 835 - 859
  • [9] RECTILINEAR STEINER TREE PROBLEM IS NP-COMPLETE
    GAREY, MR
    JOHNSON, DS
    [J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) : 826 - 834
  • [10] Gary M., 1979, COMPUTERS INTRACTABI