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 language | English (US) |
---|---|
Pages (from-to) | 3-5 |
Number of pages | 3 |
Journal | Information Processing Letters |
Volume | 31 |
Issue number | 1 |
DOIs | |
State | Published - Apr 12 1989 |
Externally published | Yes |
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