On the parallel time complexity of undirected connectivity and minimum spanning trees
Ka Wong Chong, Yijie Han, Tak‐Wah Lam · 1999
We present a new approach to finding minimum spanning trees of weighted undirected graphs on the parallel random access machine (PRAM) without concurrent-write power. This approach gives an algorithm that runs in O(log n) time using n+m processors on the EREW PRAM, settling a long-standing open problem in the literature.