DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                              ODENSE UNIVERSITY                              

                    Optimal Pointer Algorithms for Finding                   
                  Nearest Common Ancestors in Dynamic Trees                  

                               Stephen Alstrup                               
                        Department of Computer Science                       
                           University of Copenhagen                          

                      Tuesday, June 4, 1996, at 2:15 PM                      
                               The Seminar Room                              


We consider the problem of finding the  nearest common ancestor of two given
nodes x and  y (denoted by  nca(x,y)) in a  dynamic forest of  rooted trees.
Interspersed with nca-queries  are on-line commands  link(x,y), where  x but
not necessarily y is a  tree root.  The effect of a  command link(x,y) is to
combine the trees  containing x  and y by  making y  the parent  of x.  This
problem was originally proposed by Aho, Hopcroft and Ullman (SIAM J. Comput.
5(1), 115-132, 1976). We present a pointer machine algorithm, which performs
n link and m nca in time O(n +  m loglog n), matching a lower-bound by Harel
and Tarjan (SIAM J. Comput.  13(2), 338-355, 1984).  The previous best bound
on a pointer  machine was  O((n+m) log  n), due  to Sleator  and Tarjan  (J.
Comput. Syst. Sc. 26(3), 362-391, 1983).


                                                              Rolf Fagerberg