MINIMUM SPANNING-TREES FOR TREE METRICS - ABRIDGMENTS AND ADJUSTMENTS

Two properties of tree metrics are already known in the literature: tree metrics on a set X with n elements have 2n - 3 degrees of freedom; a tree metric has Robinson form with regard to its minimum spanning tree (MST), or to any such MST if several of them exist. Starting from these results, we prove that a tree metric t is entirely defined by its restriction to some set B of 2n - 3 entries. This set is easily determined from the table of t and includes the n - 1 entries of an MST A fast method for the adjustment of a tree metric to any given metric d is then obtained. This method extends to dissimilarities.