A Constant Time Algorithm for MST on RMESH
Zhang Li · Beijing Daxue Xuebao. Zirankexueban · 2006
A constant time algorithm for minimum spanning tree problem on a n2×mn2 RMESH is introduced. Based on the conclusion of simulating RMESH by PRAM, there is an O(logn) algorithm for MST on PRAM. The time complexity of these algorithms is the best so far.