Maximise Minimum Distance Between Groups of Objects

Question

You have been given a set of t items and the distance d(u,v) between each pair. Modify the minimum spanning tree algorithm, divide the t items into p groups so that the minimum distance between different groups is maximised.

I know how to use the minimum spanning tree algorithm to find a MWST, but I am confused in regards to how to adjust it to maximise the minimum distance. Any help would be greatly appreciated. Thanks

Answer 1

Hint:

• Removing the maximum-weight edge from a minimum-weight spanning tree splits the vertices into two sets.
• The distance between these two sets is at least the weight of the removed edge, otherwise that edege would not be in the minimum-weight spanning tree.

I hope this helps $\ddot\smile$