臺灣博碩士論文加值系統

一個生成樹的建構成本指的是用來建構這個生成樹的邊的權重總和。在一個生成樹Ｔ上，一個源點ｓ的傳輸成本指的是從這個源點ｓ到Ｔ的所有端點的距離總和。在一個生成樹Ｔ上，一群源點的集合Ｓ的多源傳輸成本指的是所有在這個集合Ｓ中的源點的傳輸成本的總和。建構成本與多源傳輸成本都是網路建構上的重要考量。對給定的一個圖Ｇ及一群源點的集合Ｓ，在所有生成樹中建構成本最低的稱為最小生成樹，而在所有生成樹中多源傳輸成本最低的稱為多源最小傳輸樹。通常對一組給定的(Ｇ, Ｓ)的多源最小傳輸樹不會也是最小生成樹，反之亦然。對一組給定的(Ｇ, Ｓ)，當Ｇ是一個metric graph時，我們提出一個建構生成樹的方法，使得這生成樹的建構成本小於最小生成樹的 1 + (2/(α-1))倍，同時這生成樹的多源傳輸成本小於多源最小傳輸樹的 α + 2α(k-1)(n-2)/(k(n+k-2))倍，其中k = |Ｓ|、n = |Ｖ(Ｇ)|且α ＞ 1。

摘要 ................................................. 1
Abstract ............................................. 2
Contents ............................................. 3
1.Introduction ....................................... 4
2.Basic Definitions and Notations .................... 7
3.Balancing MSTs and 2-MRCTs on Metric Graphs ........ 9
4.Balancing MSTs and k-MRCTs on Metric Graphs ........ 13
References ........................................... 18

[1] J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, volume 7, page 48~50, 1956.
[2] R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, volume 36, page 1389~1401, 1957.
[3] R. L. Graham and Pavol Hell. On the history of the minimum spanning tree problem. Annals of the History of Computing, volume 7(1), page 43~57, 1985.
[4] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, volume 1, page 269~271, 1959.
[5] B. Y. Wu. A polynomial time approximation scheme for the two-source minimum routing cost spanning trees. Journal of Algorithms, volume 44(2), page 359~378, 2002.
[6] D. S. Johnson, J. K. Lenstra, and A. H. G. Rinnooy Kan. The complexity of the network design problem. Networks, volume 8, page 279~285, 1978.
[7] B. Y. Wu, G. Lancia, V. Bafna, K. M. Chao, R. Ravi, and C. Y. Tang. A polynomial time approximation scheme for minimum routing cost spanning trees. SIAM Journal on Computing, volume 29(3), page 761-778, 1999.
[8] B. Y. Wu, K. M. Chao, and C. Y. Tang. Approximation algorithms for some optimum communication spanning tree problems. Discrete Applied Mathematics, volume 102, page 245—266, 2000.
[9] S. Khuller, B. Raghavachari, and N. Young. Balancing minimum spanning trees and shortest-path trees. Algorithmica, volume 14, page 305~321, 1995.
[10] B. Y. Wu, K. M. Chao, and C. Y. Tang. Light Graphs with Small Routing Cost. Networks, volume 39(3), page 130~138, 2002.