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)