So suppose we have a tree metric which approximates the Euclidean distance between a finite set of points. The leaves correspond to points in the original space. It may be an ultra metric, and pairwise distances in the tree may be exactly the same as the original pairwise distances (i.e. a perfect approximation), if that makes this easier to analyze.

What is the relationship between the weight of the minimum spanning tree of $S$, and the sum of the pairwise distances in the original metric space? It seems to me as though the weight of the minimum spanning tree should be related to the sum of pairwise distances, or perhaps the minimum pairwise distance.

Is the leaf set which produces the maximum weight spanning tree perhaps equivalent to a greedy solution to maximizing the sum of pairwise distances in the tree?

  • $\begingroup$ For the record, at time of writing this question has attracted a vote to close as "unclear what you're asking". I strongly disagree with this reason given $\endgroup$ – Yemon Choi May 8 '17 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.