Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/38352
 標題: Minimum Diameter Spanning Trees and Related Problems 作者: Ho, Jan-MingD.T.LeeC.H.ChangC.K.Wong 關鍵字: minimum diameter spanning treeNP-complete problemscomputational geometryminimum enclosing circlegeometric 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. URI: http://hdl.handle.net/11455/38352 ISSN: 0097-5397 Appears in Collections: 資訊科學與工程學系所

Citations: