You are given a graph G with weights we on edges and the MST T of the graph. Sup
ID: 3861928 • Letter: Y
Question
You are given a graph G with weights we on edges and the MST T of the graph. Suppose that the weight of an edge e in the graph increases from w_e to w'_e, with all the other weights remaining the same in this problem, your goal is to design a linear time algorithm to recomputed a new MST. You may assume that all weights in the graph before and after the change are distinct. Describe your algorithm. Give a brief (3-4 line) argument for correctness. Give a brief (1-2 line) argument for bounding the running time of your algorithm.Explanation / Answer
Case 1: If the edge is not in the MST, then the old MST is still the MST
Case2: If the edge e is in the MST
Remove the edge e from the MST.
Now, there are 2 connected components, find them using BFS
Iterate over all the edges and find the minimum edge that can connect the 2 disjoint components.
Add this minimum edge to get the new MST.
Corrctness: The MST contains set of all edges such that the weight of the tree is minimum. When the weight of 1 edge increases, we eliminate it and search for the next best edge to add such that the total weight remains minimum.
The BFS to identify the 2 disjoint components take O(n) time. Identifying the minimum edge to add takes O(n) time. So, the overall runtime is also O(n) where n is the number of edges.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.