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

Parallel Graph Theory Algorithms on Tree Mesh Structure

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

Abstract: 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³n）.