Chazelle's algorithm (Undirected, General MST Minimum Spanning Tree (MST))
Jump to navigation
Jump to search
Time Complexity
$O(E*\alpha(E, V))$
Space Complexity
$O(E)$ auxiliary?? words
(Seems like it uses Boruvka phases and contracts the graph, which requires $O(E)$ space, and then additional information in the tree data structure/soft heap don't require space beyond that)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
2000