Design of Data Structures for Mergeable Trees, with L. Georgiadis R. E. Tarjan. Proceeding of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 813-882, Miami, Florida, 2006. Copyright SIAM.

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(log2 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.

Note: the file below fixes a typo in the proof of Lemma 4.1.

[ pdf ]