Analysis of Geometric Minimum Diameter Minimum Cost Spanning Trees
Date Issued
2008
Date
2008
Author(s)
Chung, Chien-Yuen
Abstract
In this thesis, we consider a bicriteria problem, called minimum diameter minimum cost spanning tree (MDMCST) problem, which is to construct a minimum diameter spanning tree (MDST) among all possible minimum cost spanning trees (MST). The graph-theoretic version of this bicriteria problem has been known to be NP-hard since 1991[5]. The geometric version, however, was shown to be NP-hard much later[1]. We present two kinds of heuristic algorithms for the geometric minimum diameter and minimum cost spanning tree (GMDMCST) problem for a set of points in the plane, from the viewpoint of the MST, called MST-based heuristic algorithms, and from the viewpoint of the MDST, called MDST-based heuristic algorithms, respectively.e have implemented them using the Algorithm Benchmark System (ABS) of openCPS web portal, http://www.opencps.org [2] and performed a detailed analysis of both heuristics.n the experimental results of this benchmark system, we find that the result of MDST-based heuristic algorithms is better than the result of MST-based heuristic algorithms, but the time complexity of MDST-based heuristic algorithms is worse than MST-based heuristic algorithms.
Subjects
minimum spanning tree
minimum diameter spanning tree
minimum diameter minimum cost spanning tree
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R94922098-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):da5b7599c8f30e36bc1a137473b96592