虫孔路由二维网孔机器上的最优图论算法

• 作者: 许胤龙 郑启龙 陈国良 黄刘生
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 图论算法 并行算法 虫孔路由 网孔机器
• 年，卷（期）: 2002,（6）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 591-598
• 页数: 8页
• 分类号: TP301
• 字数: 11768字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2002.06.006

摘要

连通分量和最小生成树是图论中的两个基本问题,在许多领域都有很多应用.对于顶点数为n的图和规模为p×p的虫孔路由二维网孔机器,该文针对pn和n<pn2分别提出了连通分量算法和最小生成树算法,算法的时间复杂度分别为O(n2/p+nlogp)和O((n2/p)log2n).当plogpn时,时间复杂度为O(n2/p),此时算法的运算成本达到最优;当p=n2时,时间复杂度为O(log2n),此时连通分量和最小生成树算法都改进了存储转发路由技术下的时间复杂度下界O(n),同其它所有运行在非总线连接分布式存储的并行计算机上的算法相比,算法的时间复杂度都是最优的.