一个求图的连通分支的并行算法

已知一个无向图g(v,e),|v|=n,|e|=m,本文基于simd共享存贮模型,运用数据在图中快速传播原理,建议了一个新的求图的连通分支算法,具体来讲,在simd—crew共享存贮模型上,求图的连通分支需o(log2n)时间、o(n2/logn)处理器;而在simd—crcw共享存贮模型上需o(logn)时间、o(n2)处理器,建议的算法同著名的hirschberg算法相比,其主要差别表现在:1)采用的求解方法不同;2)建议的算法简单易懂