Bader & Cong Parallel Implementation (Undirected, General MST Minimum Spanning Tree (MST))
Jump to navigation
Jump to search
Time Complexity
$O(E \log(V)$/p)
Space Complexity
$O(V)$ total words
(Initializes and uses a constant number of arrays of size O(V) (and does work similar to work done in Boruvka/Prim algorithm))
Description
Parallel algorithm
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
PRAM/SMPs?
Year
2006
Reference
https://www.sciencedirect.com/science/article/pii/S0743731506001262