World's most popular travel blog for travel bloggers.

[Solved]: Find MST based upon new definition

, , No Comments
Problem Detail: 

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?

Asked By : user3474076

Answered By : FrankW

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback