1

Devise an algorithm that takes a weighted graph G and finds the smallest change in the cost to a non-MST edge that would cause a change in the minimum spanning tree of G.

My solution so far (need suggestions):

To make a change to the MST, we need to change the weight of a non-MST edge s.t. it is one less than the maximum edge in the path of its start vertex and end vertex in the MST.

So we can start by walking the edges of MST, and for every vertex, check if there is a non-MST edge. If there is, a bfs to reach the edge's end point (in the MST) can be done. The non-MST edge weight must be updated to one less than the maximum edge weight in the path.

This would cause the non-MST edge to be included in the MST and the previous maximum edge to be removed from MST.

Can someone tell if this solution is correct ? Thanks.

0

2 Answers 2

2

You found the idea. However, your answer needs to be tuned to show that you want to find the minimum change and not that you want to modify each non-MST edge you come across in your walk.

If this is a school question, you will also be asked to provide a proof of corectness. in order to build it, I would suggest to rely on Kruskal's proof, and to explain why your change would have Kruskal choose the modified edge instead of that other max-weight edge from the path.

0

I have an idea. So basically, we can follow the idea of the Kruskal algorithm. So if we want the MST to change, then there must be one time when the Krukal algorithm doen't choose the edge in the original MST. That edge must be the edge whose cost we are going to modify. So the algorithm is pretty clear. Follow the Kruskal algorithm, every time when we want to select a new edge e, we keep searching according to the Kruskal algorithm and find another edge e' that still doen't create a cycle. Then we calculate the minimum change in cost:w(e')-w(e)-1 .(I am not sure if the cost if limited to be an interger or not). Simply select the minimum change from above.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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