A fast algorithm for constructing trees from distance matrices.
Joseph C. Culberson and Piotr Rudnicki.
Information Processing Letters, vol 30(4), 215-220, February 1989.
Abstract
We present an algorithm which, given a tree-realizable distance matrix,
constructs the tree in optimal O(n^2) time.
We show how the algorithm can be used to test tree-realizability
of a distance matrix.
ERRATA: The time bounds for bounded degree we claimed are incorrect. See
Reyzin,
Srivasta for a corrected analysis.
A preprint is available as postscript
joe@cs.ualberta.ca