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?