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. This document analyzes several algorithms based on their approach. The most efficient such algorithms have an 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. It is proven that any separable pointer-based algorithm for the problem required omega(log n/log log n) time per operation, thus showing that our upper bound an amortized time is tight. (KR)
展开▼
