MINIMUM DIAMETER SPANNING-TREES AND RELATED PROBLEMS

被引：45
作者：
HO, JM
LEE, DT
CHANG, CH
WONG, CK
机构：
[1] NORTHWESTERN UNIV,DEPT ELECT ENGN & COMP SCI,EVANSTON,IL 60208
[2] IBM CORP,THOMAS J WATSON RES CTR,DIV RES,YORKTOWN HTS,NY 10598
[3] NYU,COURANT INST MATH SCI,DEPT COMP SCI,NEW YORK,NY 10012
来源：
SIAM JOURNAL ON COMPUTING | 1991年 / 20卷 / 05期
关键词：
MINIMUM DIAMETER SPANNING TREE; NP-COMPLETE PROBLEMS; COMPUTATIONAL GEOMETRY; MINIMUM ENCLOSING CIRCLE; GEOMETRIC STEINER TREES;
D O I：
10.1137/0220060
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The problem of finding a minimum diameter spanning tree (MDST) of a set of n points in the Euclidean space is considered. The diameter of a spanning tree is the maximum distance between any two points in the tree. A characterization of an MDST is given and a theta-(n3)-time algorithm for solving the problem is presented. The authors also show that for a weighted undirected graph, the problem of determining if a spanning tree with total weight and diameter upper bounded, respectively, by two given parameters C and D exists is NP-complete. The geometric Steiner minimum diameter spanning tree problem, in which new points are allowed to be part of the spanning tree, is shown to be solvable in O(n) time.
引用
收藏
页码：987 / 997
页数：11
相关论文
共 50 条
  • [11] Lower bounds for testing Euclidean Minimum Spanning Trees
    Ben-Zwi, Oren
    Lachish, Oded
    Newman, Ilan
    INFORMATION PROCESSING LETTERS, 2007, 102 (06) : 219 - 225
  • [12] Facility location and the geometric minimum-diameter spanning tree
    Gudmundsson, J
    Haverkort, H
    Park, SM
    Shin, CS
    Wolff, A
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 27 (01): : 87 - 106
  • [13] Diameter-Preserving Spanning Trees in Sparse Weighted Graphs
    Liu, Yue
    Huang, Jing
    GRAPHS AND COMBINATORICS, 2009, 25 (05) : 753 - 758
  • [14] Diameter-Preserving Spanning Trees in Sparse Weighted Graphs
    Yue Liu
    Jing Huang
    Graphs and Combinatorics, 2009, 25 : 753 - 758
  • [15] Parameterized complexity of finding a spanning tree with minimum reload cost diameter
    Baste, Julien
    Gozupek, Didem
    Paul, Christophe
    Sau, Ignasi
    Shalom, Mordechai
    Thilikos, Dimitrios M.
    NETWORKS, 2020, 75 (03) : 259 - 277
  • [16] On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
    Das, G
    Kapoor, S
    Smid, M
    ALGORITHMICA, 1997, 19 (04) : 447 - 460
  • [17] Computing a (1+ε)-approximate geometric minimum-diameter spanning tree
    Spriggs, MJ
    Keil, JM
    Bespamyatnikh, S
    Segal, M
    Snoeyink, J
    ALGORITHMICA, 2004, 38 (04) : 577 - 589
  • [18] Computing a (1+ε)-Approximate Geometric Minimum-Diameter Spanning Tree
    Michael J. Spriggs
    J. Mark Keil
    Sergei Bespamyatnikh
    Michael Segal
    Jack Snoeyink
    Algorithmica , 2004, 38 : 577 - 589
  • [19] Constructing Euclidean Minimum Spanning Trees and all nearest neighbors on reconfigurable meshes
    Lai, TH
    Sheng, MJ
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1996, 7 (08) : 806 - 817
  • [20] A Distributed Algorithm for Finding All Best Swap Edges of a Minimum-Diameter Spanning Tree
    Gfeller, Beat
    Santoro, Nicola
    Widmayer, Peter
    IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, 2011, 8 (01) : 1 - 12
12345