摘要
本文给出一个在CRCW-PRAM模型上运行,时间为常数的并行更新一个图的最小生成树算法.该算法所需处理器个数为O(n^2),预处理时间为O(log^2n).存贮数据所占空间为O(n^2).可以推知,该更新算法也可以在EREW-PRAM 模型上运行,且算法的复杂性相同.
In this paper,we obtain a parallel algorithmfor the edge update of minimum spanning treesin the CRCW-PRAW which uses O(n^2)proces-sors and runs in constant time.Obviously ouralgorithm is very fast in CRCW-PRAW.
出处
《微电子学与计算机》
CSCD
北大核心
1990年第4期1-6,共6页
Microelectronics & Computer
基金
国家自然科学基金
