MINIMUM DIAMETER SPANNING-TREES AND RELATED PROBLEMS

被引：46

作者：

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

共 14 条

[1]

Aho A., 1983, DATA STRUCTURES ALGO

[2]

Brown W.G., 1980, REV GRAPH THEORY

[3]

Cheriton D., 1976, SIAM Journal on Computing, V5, P724, DOI 10.1137/0205051

[4] LINEAR TIME ALGORITHMS FOR 2-VARIABLE AND 3-VARIABLE LINEAR-PROGRAMS [J].