虫孔路由Mesh上的连通分量算法及其应用

摘要：

用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log2n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log3n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.

关键词：连通分量、图论算法、并行算法、虫孔路由、网孔机器

所属期刊栏目：12

分类号：TP393(计算技术、计算机技术)

资助基金：高等学校博士学科点专项科研项目9703825

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

页数：共8页

页码：233-240