6

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?

anirudh
  • 562
  • 6
  • 23
  • Related --> http://stackoverflow.com/questions/2679472/updating-a-minimum-spanning-tree-when-a-new-edge-is-inserted – digEmAll Mar 21 '12 at 19:56
  • Here I am increasing the size of the tree and introducing n new edges, it might be the case that every edge gets replaced and still time taken should be O(n). – anirudh Mar 21 '12 at 20:01
  • When you add a vertex, do you always add edges from the new vertex to *all* the existing vertices ? If so, the new MST is just NEW-VERTEX + MST... – digEmAll Mar 21 '12 at 20:05
  • yes, to all the existing vertices – anirudh Mar 21 '12 at 20:06
  • So just take the NEW_VERTEX and link it to the MST root. Jobs done. (if I'm not missing something) – digEmAll Mar 21 '12 at 20:07
  • it is a weighted graph. That is a point of a MST - Minimum total weight. – anirudh Mar 21 '12 at 20:09
  • Oh yes, that's the missing point. Sorry I forgot the "minimum" meaning (I was thinking to the minimum number of "hops") ;) – digEmAll Mar 21 '12 at 20:21
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/9160/discussion-between-anirudh-and-digemall) – anirudh Mar 21 '12 at 20:30

2 Answers2

2

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.

Atsby
  • 2,277
  • 12
  • 14
0

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.

Pandravada Abhiram
  • 1