首页>
外文OA文献
>Concurrent threads and optimal parallel minimum spanning trees algorithm
【2h】
Concurrent threads and optimal parallel minimum spanning trees algorithm
展开▼
机译:Concurrent threads and optimal parallel minimum spanning trees algorithm
展开▼
免费
页面导航
摘要
著录项
引文网络
相似文献
相关主题
摘要
This paper resolves a long-standing open problem on whether the concurrent write capability of parallel random access machine (PRAM) is essential for solving fundamental graph problems like connected components and minimum spanning trees in O(log n) time. Specifically, we present a new algorithm to solve these problems in O(log n) time using a linear number of processors on the exclusive-read exclusive-write PRAM. The logarithmic time bound is actually optimal since it is well known that even computing the "OR" of n bits requires Ω(log n) time on the exclusive-write PRAM. The efficiency achieved by the new algorithm is based on a new schedule which can exploit a high degree of parallelism.
展开▼