A tight amortized bound for path reversal

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

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


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
Issue number1
StatePublished - Apr 12 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


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


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

Cite this