# The Complexity of Constructing Evolutionary Trees Using Experiments

Technical Report, ALCOMFT-TR-01-130, ALCOM-FT, 25 pages, 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*(*n**d* log_{d} *n*) using at most *n*
⌈ *d*/2⌉(log_{2⌈ 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 Θ(log *d*). For *d*=2 the previously best
algorithm with running time *O*(*n*log *n*) had a bound of 4*n*log *n*
on the number of experiments. By an explicit adversary argument, we
show an Ω(*n**d*log_{d} *n*) lower bound, matching our upper bounds
and improving the previous best lower bound by a
factor Θ(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*).

**Online version**
alcomft-tr-01-130.pdf (323 Kb)

**BIBT**_{E}X entry

@techreport{alcomft-tr-01-130,
author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Christian N{\o}rgaard Storm Pedersen and Anna \"Ostlin",
institution = "ALCOM-FT",
month = "May",
number = "ALCOMFT-TR-01-130",
pages = "25",
title = "The Complexity of Constructing Evolutionary Trees Using Experiments",
year = "2001"
}