Anonymous user menu

Minimum Spanning Tree
Let T be a MST of G.Suppose that we decreased the weight of one of the edge present in G but not in T.How much time will it take to construct MST for modified graph G.
Habib Mohammad Khan @habibkhan
29 Oct 2016 11:03 am

Given that we have found MST earlier , now what we have to consider is the result of the edge weight of an edge which is in graph but not in MST.

So basically we have to decide whether the decreased edge weight edge can be included and if we included which one to replace??So we have the following case:

a) We have maximum and minimum edge weight prior to this.So we check if the edge which is not now in MST on decreasing its weight makes its weight less than the maximum edge weight , then we have to check whether cycle is created due to this edge in the MST or not using cycle detection algo which  takes O(V) time where V is the no of vertices in MST.So if no cycle is created we replace the current maximum weight edge by this edge else we keep the MST unchanged.This way in total it takes O(V) time in this case.

b) Case 2 is that in case after decrementing the edge weight of the edge it is possible that it becomes less than minimum weight edge in which case it compulsorily needs to be added and as a result any of the existing edges may be replaced as graph structure may change considerably due to formation of new cycles in the graph .So we have to apply MST finding algo(Kruskal or Prim) along with cycle detection algo once again.So it will take same amount of time as Kruskals or Prims.

c) Otherwise it will be something intermediate between highest and lowest edge weights in which case we need to traverse through the entire edge weight set and update the tree once again.So we need to recompute the MST here also.So same time as Kruskals or Prims.