A Tight Amortized Bound for Path Reversal
Report ID: TR-163-88Author: Tarjan, Robert E. / Sleator, Daniel D. / Ginat, David
Date: 1988-06-00
Pages: 7
Download Formats: |PDF|
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.