
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 pointerbased 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