Loukas Georgiadis, Robert E. Tarjan
and Renato F. Werneck
Abstract
Motivated by an
application in computational topology, we consider a novel variant of
the problem
of efficiently maintaining dynamic rooted trees. This variant allows an
operation that merges two tree paths. In contrast to the standard
problem, in which only one tree arc at a time changes, a single merge
operation
can change many arcs. In spite of this, we develop a data structure
that
supports merges and all other standard tree operations in $O(\log^2
n)$ amortized time on an $n$-node forest. For the special case that
occurs in
the motivating application, in which arbitrary arc deletions are not
allowed,
we give a data structure with an $O(\log n)$
amortized
time bound per operation, which is asymptotically optimal. The
analysis
of both algorithms is not straightforward and requires ideas not
previously
used in the study of dynamic trees. We explore the design space of
algorithms
for the problem and also consider lower bounds for it.
