树网结构上的并行图论算法

• 作 者: 梁维发 陈国良
• 机 构: 中国科技大学计算机系,中国科技大学计算机系合肥,23002（?）,合肥,23002（?）
• 出 处: 计算机研究与发展
• 发表日期: 1991年1期
• 关键词: 树网结构 并行 图论 算法
• 基金项目: “863计划”资助

本文在分析树网结构的同时,发现了树网上一特殊的传播规律。利用此规律我们给出了在n 阶树网(n×n 个叶结点)上O(nlogn)步的n 阶矩阵乘法算法,此算法具有广泛的应用。运用它可有效地模拟二维网孔模型上一类算法。最后,我们给出了在n 阶树网上求n 个顶点无向图的快速桥算法,其时间复杂性为O(log~3n)。