PRAM模型模拟RMESH模型的2种方案

给出用PRAM模拟RMESH的2种方案:用n个处理器的PRAM CRCW模型模拟n×n个处理器的RMESH模型的时间复杂度为O(nlogn) ,用n2 个处理器的PRAM CRCW模型模拟n×n个处理器的RMESH模型的时间复杂度为O(logn) ,同时也给出了PRAM CREW和PRAM EREW模型模拟的时间复杂度。

最小生成树问题在RMESH上的常数时间算法

提出了在n2×mn2的RMESH模型上常数时间的最小生成树算法,并根据PRAM模拟RMESH的结论,得到了在PRAM上O(logn)时间的最小生成树算法。这2个并行算法的时间复杂度都是当前最好的。