Let a connected undirected graph G = (V, E) with edge weights and a minimum spanning tree T of G be given. Suppose the weight of an edge (u, v) in G is increased. Describe an O(V + E) algorithm to find a minimum spanning tree with this modification in edge weights.

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Observation – if the edge (u,v) doesn’t belong to T, then MST remains the same as before the modification.

If instead the edge (u,v) belongs to T, then the MST might be updated.

We build a set C1 by marking all vertices that are reachable in T from u but don’t go through v. This task can be achieved using either DFS or BFS....

This is only a preview of the solution. Please use the purchase button to see the entire solution