Technical Reports
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
|
TR-163-88
A Tight Amortized Bound for Path Reversal |
|
| Authors: | Ginat, David, Sleator, Daniel D., Tarjan, Robert E. |
| Date: | June 1988 |
| Pages: | 5 |
| Download Formats: | |
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. |
|
