A Tight Amortized Bound for Path Reversal
PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Operations Research