0
$\begingroup$

Given $T$, an MST of $G(V,E)$ connected and undirected. Assume we add an edge $e'$ with weight $w(e')$. Suggest an algorithm which takes $T$ as input, and outs $T'$ MST of $G'(V,E\cup\{e'\})$.So i thought about adding $e'$ to $T$ and removing the heaviest edge in the cycle that was formed. Can anyone suggest how to go about proving that $T'$ is indeed the MST of $G'$?

$\endgroup$
1
$\begingroup$

Please see my answer to the question "Updating an MST $T$ when the weight of an edge not in $T$ is decreased".

Before we add $e'$ with weight $w(e')$, let us add $e'$ with weight so large (or, for example, larger than the weight of every other existing edge) that $e'$ will not be in any $MST$. In particular, $T$ remains an MST with this addition.

Now let us change the weight of $e'$ to $w(e')$. Then this question becomes the same question in the linked answer above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.