Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems
Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems
复制标题
用于查找生成森林和其他基本图连接问题的最佳随机 EREW PRAM 算法
DOI：
10.1006/jagm.2000.1146
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Uri Zwick
中科院分区：
文献类型：
--
作者：
S. Halperin;Uri Zwick
我们提出了第一个随机化的O（logn）时间和O（m+n）工作的EREW PRAM算法，用于寻找具有n个顶点和m条边的无向图G=（V，E）的生成森林。我们的算法在时间、工作和空间方面是最优的。因此，我们得到了其他基本连通性问题的最优随机EREW PRAM算法，如寻找二部划分，寻找桥和双连通分量，在欧拉图中寻找欧拉游，寻找耳分解，寻找开耳分解，寻找强方向，以及寻找st-编号。
We present the first randomized O(logn) time and O(m+n) work EREW PRAM algorithm for finding a spanning forest of an undirected graph G=(V,E) with n vertices and m edges. Our algorithm is optimal with respect to time, work, and space. As a consequence we get optimal randomized EREW PRAM algorithms for other basic connectivity problems such as finding a bipartite partition, finding bridges and biconnected components, finding Euler tours in Eulerian graphs, finding an ear decomposition, finding an open ear decomposition, finding a strong orientation, and finding an st-numbering.