Accession Number:

ADA214690

Title:

A Tight Amortized Bound for Path Reversal

Descriptive Note:

Corporate Author:

PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE

Report Date:

1988-06-01

Pagination or Media Count:

7.0

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE