標題: 在平衡階層式的網路架構下建構出最小生成樹之研究
A Dominate Edge Removal Algorithm for Constructing the Minimum Spanning Tree in BHC Networks
作者: 葉奕新
I-Shin Yeh
楊千 ; 孫春在
Dr. Chyan Yang; Dr.Chuen-Tzay Suen
資訊科學與工程研究所
關鍵字: 平衡階層式; 網路; 最小生成樹; 支配邊刪除;Dominate Edge Removal; Minimum Spanning Tree; BHC Networks
公開日期: 1993
摘要: 在此篇論文中, 我們提出了一個平行且分散式的演算法, 即刪除支配邊的
演算法。這個演算法可在一個平衡階層式的網路架構下, 建構出一個最小
生成樹。此演算法採用的觀念是: 藉著網路的平衡階層性, 用 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).
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT820394015
http://hdl.handle.net/11536/57911
Appears in Collections:Thesis