-
题名虫孔路由二维网孔机器上的最优图论算法
被引量:1
- 1
-
-
作者
许胤龙
黄刘生
郑启龙
陈国良
-
机构
中国科学技术大学计算机科学技术系
合肥国家高性能计算中心
-
出处
《计算机学报》
EI
CSCD
北大核心
2002年第6期591-598,共8页
-
文摘
连通分量和最小生成树是图论中的两个基本问题 ,在许多领域都有很多应用 .对于顶点数为 n的图和规模为 p× p的虫孔路由二维网孔机器 ,该文针对 p n和 n <p n2 分别提出了连通分量算法和最小生成树算法 ,算法的时间复杂度分别为 O(n2 / p +nlogp)和 O((n2 / p) log2 n) .当 plogp n时 ,时间复杂度为 O(n2 / p ) ,此时算法的运算成本达到最优 ;当 p =n2 时 ,时间复杂度为 O(log2 n) ,此时连通分量和最小生成树算法都改进了存储转发路由技术下的时间复杂度下界 O(n) ,同其它所有运行在非总线连接分布式存储的并行计算机上的算法相比 。
-
关键词
虫孔路由
二维网孔机器
最优图论算法
并行算法
计算机
-
Keywords
graph algorithm, parallel algorithm, wormhole routing, mesh
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-