Suppose you are given an undirected graph G with weighted edges and a minimum sp

Question

Suppose you are given an undirected graph G with weighted edges and a minimum spanning tree T of G.

• Design an algorithm to update the minimum spanning tree when the weight of a single edge e is increased.

• Design an algorithm to update the minimum spanning tree when the weight of a single edge e is decreased.

In both cases, the input to your algorithm is the edge e and its new weight; your algorithms should modify T so that it is still a minimum spanning tree. Analyze the running time of your algorithms and prove the correctness.

Explanation / Answer

1. When edge weight is increased:
- If the edge e is originally not in the MST, then the MST is the same as increasing weight of that edge would not affect the MST.
- If e was in the original MST, then remove e from the MST. Now, the MST is divided into two connected components. Find these using a simple DFS(as graph is undirected, connected componenets can be found out using a DFS).
- Let these components be C1 and C2. Both are MSTs of their respective connected components.
- Iterate over each such edge which connects a vertex from C1 to a vertex of C2. Take the minimum weighted edge of these edges and add to MST. This is the answer.
- Time complexity - O(V+E), O(V) for the DFS and O(E) for iterating over the edges.

2. When edge weight is decreased:
- If e is originally in the MST, then the MST is the same as decreasing weight of that edge would not affect the MST.
- If e is not in the MST, then do a DFS from V1 and find the path that connects V1 to V2. (V1 and V2 are end points of e).
- Now find the max weight edge e' that is in the path V1->V2. If that weight of e' > wt of e, then replace e with e' else MST remains the same.
- Time complexity- O(V), O(V) for DFS and O(V) for finding max weighted edge in the path.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.