Accession Number : ADA195823

Title :   Amortized Analysis of Algorithms for Set Union with Backtracking. Revision,

Corporate Author : PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE

Personal Author(s) : Westbrook, Jeffrey ; Tarjan, Robert E

PDF Url : ADA195823

Report Date : Mar 1988

Pagination or Media Count : 23

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. 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)

Descriptors :   *ALGORITHMS, *SET THEORY, OPERATION, REDUCTION, STANDARDIZATION, TIME

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE