-1
$\begingroup$

Redefine the weight of a spanning tree to be the weight of the maximum weight edge in the tree (i.e. the weight of the tree is no longer the sum of the weights of all the edges in the tree, only the weight of the edge with the maximum weight). How would you derive an efficient algorithm to compute the minimum weight spanning tree under this new definition? Do not assume the edge weights are distinct.

A brute force approach would obviously be to compute all possible MSTs, then sort them based on their maximum weighted edge, and choose the smallest one. This is not efficient however, but I am having trouble seeing how to do this. Any ideas?

$\endgroup$
2
$\begingroup$

Every MST according to the original definition is also optimal according to your new definition. (The proof of this statement is left as an exercise; it is not that hard.) So any MST algorithm will do the job.

$\endgroup$
  • $\begingroup$ That makes sense that using any algorithm will work because under both definitions we are getting the same graph. I went with Kruskal's. The part that I am still struggling with is the proof. I guess because the edge weights cannot be assumed to be distinct how do I know that every new MST will have the same maximum weight edge and be optimal? $\endgroup$ – user3474076 May 13 '14 at 18:20

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.