Dynamic Minimum Spanning Tree

Question

I want to create a dynamic minimum spanning tree. I have an existing MS tree over n vertices, and I add another vertex and edges to all existing vertices from this new vertex. How can I effectively update MST for a new chart? O (n) would be optimal. Can I also efficiently remove the vertex operation?

Answer 1

O(n log n) using the Kruskal algorithm. The basic idea is that any edges not used in the original MST will also not be used in the new MST. So, just sort n new edges O(n log n) , combine this sorted list with the list of edges of the old MST (which you saved in sorted order, right?) O(n) , then run the Kruskal algorithm again as a result of sorting the list of edges O(n)-ish .