一個解決最小展開樹的快速平行計算機方法

Abstract

多年來，在一個加權連結的圖形 G = (V，E) 上找尋它的最小展開樹 ( Minimum Spa nning Tree Problem )廣汎地為人所研究著。在此篇論文中，我們依 Sollin 所提出 的方法，提出一個平行時間複雜度為 O(α(logn，logn)logn)的平行計算機方法；它 使用了 O(n□)個計算單元。所根據的計算模型是 Connection Machine，一個具有共 通性相互連接網路的 SIMD 機器。其中 G = (V，E) 是問題給定的加權連結圖形 ︱V ︱ = n，︱E︱ = m ；α(m，n)是 Inverse Ackermann's函數。