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

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1988
Accession Number
ADA195823

Entities

People

  • Jeffrey Westbrook
  • Robert Tarjan

Organizations

  • Princeton University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Buildings And Structures
  • Compression
  • Computer Science
  • Computers
  • Inequalities
  • Military Research
  • Models
  • New Jersey
  • Semantic Models
  • Sequences
  • Splitting
  • Time Intervals
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.

Technology Areas

  • Space