Technical Reports


Display by Author:
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
Search by for:

TR-163-88
A Tight Amortized Bound for Path Reversal
Authors: Ginat, David, Sleator, Daniel D., Tarjan, Robert E.
Date:June 1988
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.