ALCOMFT-TR-01-130

Gerth Stølting Brodal, Rolf Fagerberg, Christian N. S. Pedersen and Anna Östlin
The Complexity of Constructing Evolutionary Trees Using Experiments
Århus. Work package 4. May 2001.

Abstract: We present tight upper and lower bounds for the problem of constructing evolutionary trees in the experiment model. We describe an algorithm which constructs an evolutionary tree of n species in time O(nd log_d n) using at most n \ceil{ d/2 } (log_{2\ceil{ d/2 }-1} n + O(1)) experiments for d>2, and at most n(log n + O(1)) experiments for d=2, where d is the degree of the tree. This improves the previous best upper bound by a factor Theta(log d). For d=2 the previously best algorithm with running time O(nlog n) had a bound of 4nlog n on the number of experiments. By an explicit adversary argument, we show an Omega(ndlog_d n) lower bound, matching our upper bounds and improving the previous best lower bound by a factor Theta(log_d n). Central to our algorithm is the construction and maintenance of separator trees of small height. We present how to maintain separator trees with height log n+O(1) under the insertion of new nodes in amortized time O(log n). Part of our dynamic algorithm is an algorithm for computing a centroid tree in optimal time O(n).

Postscript file: ALCOMFT-TR-01-130.ps.gz (127 kb).