question archive For an undirected, connected graph G = (V, E) with weights w(e) > 0 for each edge e ∈E, there is a set of edges T which define the MST of G
For an undirected, connected graph G = (V, E) with weights w(e) > 0 for each edge e ∈E, there is a set of edges T which define the MST of G
Subject:Computer SciencePrice:9.82 Bought3
For an undirected, connected graph G = (V, E) with weights w(e) > 0 for each edge e ∈E, there is
a set of edges T which define the MST of G. Unfortunately one of the edges e∗= (u, v) which is in
the MST is deleted from both the graph G and the set of edges T (no other edges change).
Given G −e∗and the updated set T −e∗, define an algorithm to build a MST for the new graph.
Note: G is connected, and G −e∗is also connected. Your algorithm should be correct and faster in
asymptotic Big O(·) notation than building a MST from scratch (so using Prim's or Kruskal's will
receive little credit).
Purchase A New Answer
Custom new solution created by our subject matter experts
GET A QUOTE
Answer Preview
refer to the solution below
Step-by-step explanation
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|).
