CODEWITHSUNDEEP
algorithminsertminimum-spanning-tree
anirudh
anirudh

Reputation: 562

dynamic minimum spanning tree

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?

Upvotes: 6

Views: 7140

Answers (2)

Pandravada Abhiram
Pandravada Abhiram

Reputation: 1

This problem can be solved using locality sensitive ordering. Please refer to the this paper. They discuss on the cost of forming a dynamic minimum spanning tree and that it gives a (1+epsilon) approximation over the most optimal solution.

Upvotes: 0

Atsby
Atsby

Reputation: 2327

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.

Upvotes: 2

Related Questions