World's most popular travel blog for travel bloggers.

# [Solved]: Find MST based upon new definition

, ,
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?

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.

Question Source : http://cs.stackexchange.com/questions/24647

3.2K people like this