| 受限SIMD PRAM模型上的高效并行图算法 |
| |
| 引用本文： | 马军,马绍汉. 受限SIMD PRAM模型上的高效并行图算法[J]. 山东大学学报(理学版), 1993, 0(3) |
| |
| 作者姓名： | 马军 马绍汉 |
| |
| 作者单位： | 山东大学计算机科学系，山东大学计算机科学系 |
| |
| 摘 要： | 在限定处理机个数的 CREW PRAM并行计算模型上,给出了图论中一些基本问题的并行算法.所给并行算法的费用c(n)=p(n)*t(n)是目前已知的最好结果,其中p(n),t(n)分别是对一具有n个顶点图实施并行算法所用处理机的个数和最坏情况下的时间复杂性。
|
| 关 键 词： | CREW PRAM并行计算模型 图论算法 并行算法 |
PARALLEL GRAPH ALGORITHMS ON LIMITED SIMD PRAM MODELS |
| |
| Ma Jun,Ma Shaohan Dept. of Computer Science,Shandong Univ.,Jinan. PARALLEL GRAPH ALGORITHMS ON LIMITED SIMD PRAM MODELS[J]. Journal of Shandong University, 1993, 0(3) |
| |
| Authors: | Ma Jun Ma Shaohan Dept. of Computer Science Shandong Univ. Jinan |
| |
| Abstract: | The parallel algorithms for some basic graph problems are given on the SIMD PRAM computation models with limited number of processors. The parallel cost, c(n)=p(n)*t(n), of these algorithms are the best result known so far. p(n), t(n) represent the num-ber of processors used and the worst case time complexity of a parallel algorithm for a graph with n vertice respectively. |
| |
| Keywords: | CREW PRAM computation models graph algorithm parallel algorithm |
| 本文献已被 CNKI 等数据库收录！ |
