Please use this identifier to cite or link to this item:
標題: Minimum Diameter Spanning Trees and Related Problems
作者: Ho, Jan-Ming
關鍵字: minimum diameter spanning tree
NP-complete problems
computational geometry
minimum enclosing circle
geometric Steiner trees
摘要: 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 (n^3)$-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.
ISSN: 0097-5397
Appears in Collections:資訊科學與工程學系所



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.