Fast Self-Stabilizing Minimum Spanning Tree Construction Using Compact Nearest Common Ancestor Labeling Scheme

Lélia Blin, Shlomi Dolev, Maria Gradinariu Potop-Butucaru +1

We present a novel self-stabilizing algorithm for minimum spanning tree (MST) construction. The space complexity of our solution is $O({\log }^{2}n)$ bits and it converges in $O(n^2)$ r…