A Tight Amortized Bound for Path Reversal

Abstract

Path reversal is a form of path compression used in a disjoint set union algorithm and a mutual exclusion algorithm. We derive a tight upper bound on the amortized cost of path reversal.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1988
Accession Number
ADA214690

Entities

People

  • Daniel D. Sleator
  • David Ginat
  • Robert Tarjan

Organizations

  • Princeton University

Tags

DTIC Thesaurus Topics

  • Additives (Chemicals)
  • Air Force
  • Algorithms
  • Binomials
  • Compression
  • Computers
  • Contracts
  • Data Compression
  • Inequalities
  • Maryland
  • Mathematics
  • Reasoning
  • Sequences
  • Standards

Fields of Study

  • Computer science

Readers

  • Mathematical Modeling and Probability Theory.
  • Parallel and Distributed Computing.