Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary)
Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary)
复制标题
在对数并行时间内查找双连通分量并计算树函数（扩展摘要）
DOI：
--
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
U. Vishkin
中科院分区：
文献类型：
--
作者：
R. Tarjan;U. Vishkin
本文提出了一种新的无向图块（双连通分支）的求法。串行实现在0[n+m]时间和空间中在n个顶点和m条边的图上运行。在一个并行读、并行写的RAM上，使用0[n +m]个处理器，在0[log n]时间和0[n +m]空间内并行实现。另一种实现在0[n/sup 2/p]时间和0[n/sup 2/]空间中运行，使用任意数量的p n/sup 2/log/sup 2/-n个处理器，在并发读，排他写的并行RAM上。后一种算法具有最佳的加速比，假设输入的邻接矩阵表示。本文介绍了一种通用的算法技术，它简化和改进了树上各种函数的计算。这种技术通常需要0（log n）时间，使用排他读排他写并行RAM上的0（n）空间。
We propose a new algorithm for finding the blocks (biconnected components) of an undirected graph. A serial implementation runs in 0[n+m] time and space on a graph of n vertices and m edges. A parallel implmentation runs in 0[log n] time and 0[n+m] space using 0[n+m] processors on a concurrent-read, concurrent-write parallel RAM. An alternative implementation runs in 0[n/sup 2/p] time and 0[n/sup 2/] space using any number p ⩽ n/sup 2/log/sup 2/-n of processors, on a concurrent-read, exclusive-write parallel RAM. The latter algorithm has optimal speedup, assuming an adjacency matrix representation of the input. A general algorithmic technique which simplifies and improve computation of various functions on tress is introduced. This technique typically requires 0(log n) time using 0(n) space on an exclusive-read exclusive-write parallel RAM.