We present a polynomial time algorithm for computing the refined Buneman tr
ee, thereby making it applicable for tree reconstruction on large data sets
. The refined Buneman tree retains many of the desirable properties of its
predecessor, the well-known Buneman tree, but has the practical advantage t
hat it is typically more refined. (C) 1998 Elsevier Science Ltd. All rights
reserved.