A tight amortized bound for path reversal

David Ginat, Daniel D. Sleator, Robert E. Tarjan

Research output: Contribution to journalArticle

15 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)3-5
Number of pages3
JournalInformation Processing Letters
Volume31
Issue number1
DOIs
StatePublished - Apr 12 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Analysis of algorithms
  • amortized efficiency
  • data structures
  • disjoint set union
  • path compression

Fingerprint Dive into the research topics of 'A tight amortized bound for path reversal'. Together they form a unique fingerprint.

  • Cite this