树网结构上的并行图论算法

Parallel Graph Theory Algorithms on Tree Mesh Structure

本文在分析树网结构的同时,发现了树网上一特殊的传播规律。利用此规律我们给出了在n 阶树网(n×n 个叶结点)上O(nlogn)步的n 阶矩阵乘法算法,此算法具有广泛的应用。运用它可有效地模拟二维网孔模型上一类算法。最后,我们给出了在n 阶树网上求n 个顶点无向图的快速桥算法,其时间复杂性为O(log^3n)。

In this paper,we present some parallel algorithms for graph problem on the treemesh structure with n×n leaf-nodes,including a n-order matrix multiplication algorithm in timeO(nlogn),an algorithm of finding all-pairs shortest-path of n-vertex digraph in time O(nlogn),anda bridge-finding algorithm of n-vertex undirected graph in time O(log^3n).