For a metric $(X,d)$ a weighted graph $G= (V, E, w)$ is called a realization of $d$ if (i) $X \subseteq V$ (ii) $d_g(x,y) = d(x,y)$ for all $x, y \in X$.
A realization is called {\em optimal} if the sum $\sum_{xy \in E} w(xy)$ is minimal among all the realizations. It is known that to find an optimal realization is NP-hard in general. But for the case of a tree-metric, i.e. a metric coming from a tree, it is the underlying (weighted) tree.
In this talk I will discuss properties of optimal realizations and why they are useful for the area of phyogenetic methods.
view more