Amortized Analysis of Algorithms for Set Union with Backtracking

Abstract:

Mannila and Ukkonen have studied a variant of the classical disjoint set union (equivalence) problem in which an extra operation, called deunion, can undo the most recently performed union operation not yet undone. They proposed a way to modify standard set union algorithms to handle deunion operations. We analyze several algorithms based on their approach. The most efficient such algorithms have amortized running time of O(log n/log log n) per operation, where n is the total number of elements in all the sets. These algorithms use O(n log n) space, but the space usage can be reduced to O(n) by a simple change. We prove that any separable pointer-based algorithm for the problem requires omega(log n/log log n) time per operation, thus showing that our upper bound is tight.