基于CREW遍历图的一种并行算法

摘要：

针对串行算法模型下基于顶点遍历图的情况,提出了一种在 CREW PRAM并行模型下遍历无向图的算法.该算法是找出无向图的一棵最短路径生成树,由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路,运用欧拉回路技术计算前缀和,前缀和所对应的顶点即为遍历无向图的顺序.得出了该算法时间复杂度为O(n+logn) 的结论.

关键词：遍历、无向图、并行算法、生成树

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2006-10-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：12-14