Approximating geodesic tree distance

Billera, Holmes, and Vogtmann introduced an intriguing new phylogenetic tree metric for weighted trees with useful properties related to statistical analysis. However, the best known algorithm for calculating this distance is exponential in the number of leaves of the trees compared. We point out that lower and upper bounds for this distance, which can be calculated in linear time, can differ by at most a multiplicative factor of .