在平衡階層式的網路架構下建構出最小生成樹之研究

Abstract

在此篇論文中, 我們提出了一個平行且分散式的演算法, 即刪除支配邊的 演算法。這個演算法可在一個平衡階層式的網路架構下, 建構出一個最小 生成樹。此演算法採用的觀念是: 藉著網路的平衡階層性, 用 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).