臺灣博碩士論文加值系統

在此篇論文中, 我們提出了一個平行且分散式的演算法, 即刪除支配邊的
演算法。這個演算法可在一個平衡階層式的網路架構下, 建構出一個最小
生成樹。此演算法採用的觀念是: 藉著網路的平衡階層性, 用 bottom-up
的方式漸次將小的生成樹平行地合併成大的生成樹, 直到建構出最高階層
的最小生成樹為止。假設此平衡階層式的網路架構, 共包含了 k 個階層
和 n 個節點, 則此演算法的通訊時間複雜度是 O(n), 而計算時間複雜度
是 O(log n)。

A parallel and distributed algorithm, i.e., the Dominate Edge
Removal algorithm, is presented that constructs the minimum
spanning tree in a Balanced Hierarchy Clustered (BHC) networks.
The idea of the DER algorithm is taking bottom-up recursive
merge until the final minimum spanning tree is constructed. It
merges two smaller minimum spanning trees to form a larger
minimum spanning tree in parallel by the balance and hierarchy
of the BHC networks. For a BHC network with k levels and n
nodes, the communication time complexity is O(n) and the
computation time complexity is O(log n).