最小直徑最小成本生成樹之分析

Analysis of Geometric Minimum Diameter Minimum Cost Spanning Trees

鐘健元(Chien-Yuen Chung)

指導教授 ： 李德財

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.00194

摘要

在此論文中，我們將討論最小直徑最小成本生成樹的問題，最小直徑最小成本生成樹就是在所有的最小生成樹當中去找到直徑最小的。這個圖論版本的問題在1991年被證明是NP-hard[5]。而計算幾何的版本也在隨後被證明是NP-hard[1]。我們將會對於在平面上給定一個點集合去計算幾何的最小直徑最小成本生成樹這個問題給兩種類型的經驗法則演算法。一種是從最小成本生成樹的觀點，另一種則是從最小直徑生成樹。
我們已經把以上的演算法實作在平台Algorithm Benchmark System (ABS) of openCPS web portal，http://www.opencps.org [2]上面，我們也將會有詳細的分析敘述。
根據這個測試系統我們給定以最小直徑生成樹為觀點的演算法是能夠比以最小成本生成樹為觀點的計算出比較好的結果，但是相對的最小直徑生成樹為觀點的演算法的時間複雜度就高出了許多。

關鍵字

最小生成樹 ； 最小半徑生成樹

並列摘要

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.
We 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.
In 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.

並列關鍵字

minimum spanning tree ； minimum diameter spanning tree ； minimum diameter minimum cost spanning tree

參考文獻

[1] Dae Young Seo “On the Complexity of Bicriteria Spanning Tree Problems for

a Set of Points in the Plane”, December 1999.

[3] J. B. Kruskal “On the Shortest Spanning Subtree of a Graph and the Traveling

[4] R. C. Prim “Shortest Connection Networks and Some Generalizations”, Bell

System Tech. J., 1957.