Question

MST

For an undirected graph G = (V, E) with weights w(e) > 0 for each edge e ∈ E, you are given a MST T. Unfortunately one of the edges e* = (u, z) which is in the MST T is deleted from the graph G (no other edges change). Give an algorithm to build a MST for the new graph. Your algorithm should start from T.

Note: G is connected, and G − e* is also connected.

Explain your algorithm in words and use the algorithms from class as black-box subroutines.

Clearly state and explain the running time of your algorithm. To receive credit, your algorithm should be correct and faster in O() than building a MST from scratch (so don’t use Prim’s or Kruskal’s, even part of Kruskal’s).

Answer 1

As the edge e*(u,z) has been deleted, let Tu, Tz be the sub tree of T after deletion of e*.

Now, we can find the set of vertices in Tu and Tv in O(|V|+|E|) time.

Then, find set of edges with one end point in Tu and another end point in Tz, find the edge with smallest weight among those, add that edge(say e) to the MST, this is the modified MST after deletion of e*.

Finding smallest weight edge also takes O(|E|) time, so overall complexity of our algorithm is O(|V|+|E|).