Abstract (Stephen Alstrup)

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).
Last modified: May 14, 1996.
Kim Skak Larsen (kslarsen@imada.sdu.dk)