DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                    UNIVERSITY OF SOUTHERN DENMARK, ODENSE                   

     The Complexity of Constructing Evolutionary Trees Using Experiments     

                                 Anna Östlin                                 
                    BRICS, Department of Computer Science                    
                             University of Aarhus                            

                    Tuesday, December 11, 2001, at 2:15 PM                   
                               The Seminar Room                              


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(nd  log_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, which may be of independent interest.

This work is joint with Gerth Stølting Brodal, Rolf Fagerberg, and Christian
N. S. Pedersen and has appeared in the proceedings of the 28th International
Colloquium on Automata, Languages,  and Programming, volume  2076 of Lecture
Notes in Computer Science, pages 140-151. Springer Verlag, Berlin, 2001.


                                                            Host: Joan Boyar