Recognition of Tree Metrics
Hans‐Jürgen Bandelt · SIAM Journal on Discrete Mathematics · 1990
A tree metric on a set of n points (objects) is realized by a weighted undirected tree whose tips are labelled by the objects. It is well known that tree metrics are characterized by the so-called 4-point condition. In this note it is shown that a metric d is a tree metric if and only if the Farris transform of d qualifies as an ultrametric. Based on this, an $O(n^2 \log n)$ procedure is established for recognizing tree metrics on an n-set.