ON THE NUMBER OF MINIMAL-1-STEINER TREES

被引：1
|
作者：
ARONOV, B
BERN, M
EPPSTEIN, D
机构：
[1] XEROX CORP,PALO ALTO RES CTR,PALO ALTO,CA 94304
[2] UNIV CALIF IRVINE,DEPT INFORMAT & COMP SCI,IRVINE,CA 92717
来源：
DISCRETE & COMPUTATIONAL GEOMETRY | 1994年 / 12卷 / 01期
关键词：
D O I：
10.1007/BF02574363
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We count the number of nonisomorphic geometric minimum spanning trees formed by adding a single point to an n-point set in d-dimensional space, by relating it to a family of convex decompositions of space. The O(n(d)log(2d2-d)n) bound that we obtain significantly improves previously known bounds and is tight to within a polylogarithmic factor.
引用
收藏
页码：29 / 34
页数：6
相关论文
共 50 条
  • [1] Steiner minimal trees
    Rayward-Smith, VJ
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1998, 49 (12) : 1304 - 1305
  • [2] STEINER MINIMAL TREES
    GILBERT, EN
    POLLAK, HO
    SIAM JOURNAL ON APPLIED MATHEMATICS, 1968, 16 (01) : 1 - &
  • [3] On the Number of Steiner Trees in a Graph
    Sen, A.
    Zhou, C.
    Mazumder, A.
    Das, A.
    Basu, K.
    Walkowiak, K.
    2020 16TH INTERNATIONAL CONFERENCE ON THE DESIGN OF RELIABLE COMMUNICATION NETWORKS DRCN 2020, 2020,
  • [4] Approximations for Steiner Trees with Minimum Number of Steiner Points
    DONGHUI CHEN
    DING-ZHU DU
    XIAO-DONG HU
    GUO-HUI LIN
    LUSHENG WANG
    GUOLIANG XUE
    Journal of Global Optimization, 2000, 18 : 17 - 33
  • [5] Approximations for Steiner trees with minimum number of Steiner points
    Chen, DH
    Du, DZ
    Hu, XD
    Lin, GH
    Wang, LS
    Xue, GL
    THEORETICAL COMPUTER SCIENCE, 2001, 262 (1-2) : 83 - 99
  • [6] Approximations for Steiner trees with minimum number of Steiner points
    Chen, DG
    Du, DZ
    Hu, XD
    Lin, GH
    Wang, LS
    Xue, GL
    JOURNAL OF GLOBAL OPTIMIZATION, 2000, 18 (01) : 17 - 33
  • [7] STEINER MINIMAL TREES FOR BAR WAVES
    堵丁柱
    黄光明
    Acta Mathematicae Applicatae Sinica(English Series), 1987, (03) : 246 - 256
  • [8] GENERATION OF MINIMAL TREES WITH A STEINER TOPOLOGY
    CHANG, SK
    JOURNAL OF THE ACM, 1972, 19 (04) : 699 - &
  • [9] ADVANCE IN COMPUTATION OF STEINER MINIMAL TREES
    BOYCE, WM
    SEERY, JB
    SIAM REVIEW, 1974, 16 (01) : 117 - 117
  • [10] STEINER MINIMAL TREES WITH RECTILINEAR DISTANCE
    HWANG, FK
    SIAM JOURNAL ON APPLIED MATHEMATICS, 1976, 30 (01) : 104 - 115
12345