Finding a Minimum Spanning Tree given the old MST

Question

In a sample problem, I'm given a MST T for a weighted graph G = (V, E). The question is, if a new vertex v and all its edges are to be added to the graph, what is an o(|V|log|V|) algorithm to compute the new MST of this new G* = (V U v, E*).

My only idea so far is:

add min( out(v) ) to T
for each edge e in out(v) do
  let u be the other vertex of e
  if there exists a lower weight path from v to u then
    remove all edges in that path from T
    add e to T

Two problems:

1. What do I do with the vertices that may have gotten disconnected
2. This is definitely not O(|V|log|V|)

How can I do this?

Answer 1

You can also do it in linear time (if the number of the new edges(say k) is considerably less comparing to n). We know new MST should cover the new vertex. So at least one of the new edges must be added. So the edge with the smallest value must be added to MST (you can prove this); it might happen that more than one new edge changes. So sort new edges from in ascending order Add the first one to the graph; now we have a new cycle. Doing graph traversal find the cycle and delete the edge with the maximum value from this cycle. Now add the other new edge and repeat the procedure.

The complexity is (n+m) times the number of newly added edges(roughly linear).

Answer 2

See ultimately you know that your MST will be among the edges already in th MST and the new edges added

So add all the new edges you will get a graph. Do any normal MST algorithm (Boruvka, Kruskal, Prims) on this and you will have your solution.

Since the edges in this is = (V-2) Initially (V-1) added = 2V-1 the algorithms will achieve the time bound you need.