dynamic minimum spanning tree

Question

I want to make a dynamic minimum spanning tree. I have an existing MS tree over n vertices and I add one more vertex and edges to all the existing vertices from this new vertex. How can I update the MST for the new graph efficiently? O(n) would be optimal. Can I also make delete vertex operation efficient?

Answer 1

O(n log n) using Kruskal's algorithm. The key idea is any edges not used in the original MST will not be used in the new MST either. So just sort the n new edges O(n log n), merge this sorted list with the list of edges of the old MST (which you kept in sorted order, right?) O(n), then run Kruskal's algorithm anew on the resulting sorted list of edges O(n)-ish.