Suppose given complete undirected weighted graph $G=(V,E)$ with $n$ vertices, also we have Minimum spanning tree $T$ that obtained from $G$. if we decrease the weight of $n$ arbitrary edges, how we can find MST of $G$ without computing MST of $G$?

My idea is as follow:

  1. create a graph $T'$ with $n$ vertices that contains those edges that decreased.

  2. Compute MST $T''$ from $T\cup T'$.

now suppose MST of $G$ after decrease edges weights be $T'''$, but I can't prove that $T'''=T''$.



Browse other questions tagged or ask your own question.