A tight amortized bound for path reversal

David Ginat; Daniel D. Sleator; Robert E. Tarjan

doi:10.1016/0020-0190(89)90101-4

A tight amortized bound for path reversal

David Ginat, Daniel D. Sleator, Robert E. Tarjan

Research output: Contribution to journal › Article › peer-review

19 Scopus citations

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.

Original language	English (US)
Pages (from-to)	3-5
Number of pages	3
Journal	Information Processing Letters
Volume	31
Issue number	1
DOIs	https://doi.org/10.1016/0020-0190(89)90101-4
State	Published - Apr 12 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Analysis of algorithms
amortized efficiency
data structures
disjoint set union
path compression

Access to Document

10.1016/0020-0190(89)90101-4

Cite this

@article{c247bff04e5c4838b6d6f6492e657a15,

title = "A tight amortized bound for path reversal",

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.",

keywords = "Analysis of algorithms, amortized efficiency, data structures, disjoint set union, path compression",

author = "David Ginat and Sleator, {Daniel D.} and Tarjan, {Robert E.}",

note = "Funding Information: * Research partially supported by DARPA, ARPA order 4976, amendment 19, monitored by the Air Force Aeronautics Laboratory under Contract No. F33615-87-C 1499, by the National Science Foundation under Grant No. CCR 8658139, and by AT&T Bell L&oratories. *a Research partially supported by NSF Grant No. DCR-8605962 and ONR Contract No. NOOOM-87-K-0467.",

year = "1989",

month = apr,

day = "12",

doi = "10.1016/0020-0190(89)90101-4",

language = "English (US)",

volume = "31",

pages = "3--5",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - A tight amortized bound for path reversal

AU - Ginat, David

AU - Sleator, Daniel D.

AU - Tarjan, Robert E.

N1 - Funding Information: * Research partially supported by DARPA, ARPA order 4976, amendment 19, monitored by the Air Force Aeronautics Laboratory under Contract No. F33615-87-C 1499, by the National Science Foundation under Grant No. CCR 8658139, and by AT&T Bell L&oratories. *a Research partially supported by NSF Grant No. DCR-8605962 and ONR Contract No. NOOOM-87-K-0467.

PY - 1989/4/12

Y1 - 1989/4/12

N2 - 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.

AB - 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.

KW - Analysis of algorithms

KW - amortized efficiency

KW - data structures

KW - disjoint set union

KW - path compression

UR - http://www.scopus.com/inward/record.url?scp=0024640686&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024640686&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(89)90101-4

DO - 10.1016/0020-0190(89)90101-4

M3 - Article

AN - SCOPUS:0024640686

SN - 0020-0190

VL - 31

SP - 3

EP - 5

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

A tight amortized bound for path reversal

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this