The Complexity of Constructing Evolutionary Trees Using Experiments

Gerth Stølting Brodal, Rolf Fagerberg, Christian Nørgaard Storm Pedersen, and Anna Östlin

Technical Report, ALCOMFT-TR-01-130, ALCOM-FT, 25 pages, May 2001.


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 logd n) using at most nd/2⌉(log2⌈ 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(nlog n) had a bound of 4nlog n on the number of experiments. By an explicit adversary argument, we show an Ω(ndlogd n) lower bound, matching our upper bounds and improving the previous best lower bound by a factor Θ(logd 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)

BIBTEX entry

  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"