| ∑树结构与更新最小生成树的并行算法 |
| |
| 引用本文： | 江正. ∑树结构与更新最小生成树的并行算法[J]. 中国科学技术大学学报, 1990, 0(2) |
| |
| 作者姓名： | 江正 |
| |
| 作者单位： | 北京计算机学院 |
| |
| 摘 要： | 更新最小生成树问题,即已知图的最小生成树,当图的某条边的赋值被改变,如何快速有效的求新出的最小生成树.本文引进了∑-树结构,并以此获得了一个快速有效的更新最小生成树的并行算法,并行时间为O(logn),处理器个数为O(n~(4/(?)),计算模型为CREW-PRAM.其中n 为图的顶点个数,而且,进行预处理所需的时问也只需O(log~2n),处理器个数为O(n~(?)),存贮数据所需的空间为O(n~(?)).
|
| 关 键 词： | 并行计算 PRAM 模型 更新最小生成树 ∑树 |
Sum-tree Structure and Parallel Algorithm for Updating Minimum Spanning Tree |
| |
| Jiang Zheng. Sum-tree Structure and Parallel Algorithm for Updating Minimum Spanning Tree[J]. Journal of University of Science and Technology of China, 1990, 0(2) |
| |
| Authors: | Jiang Zheng |
| |
| Affiliation: | Beijing Computer Institute |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
|
