The Complexity of Constructing Evolutionary Trees Using Experiments

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

In Proc. 28th International Colloquium on Automata, Languages, and Programming, volume 2076 of Lecture Notes in Computer Science, pages 140-151. Springer Verlag, Berlin, 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, which may be of independent interest.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2001. All rights reserved.

Online version

icalp01.pdf (151 Kb)




BIBTEX entry

  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Christian N{\o}rgaard Storm Pedersen and Anna \"Ostlin",
  booktitle = "Proc. 28th International Colloquium on Automata, Languages, and Programming",
  doi = "10.1007/3-540-48224-5_12",
  isbn = "978-3-540-42287-7",
  pages = "140-151",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "The Complexity of Constructing Evolutionary Trees Using Experiments",
  volume = "2076",
  year = "2001"

Other versions