Worst-Case Analysis of Set Union Algorithms

Robert E. Tarjan; Jan van Leeuwen

doi:10.1145/62.2160

Worst-Case Analysis of Set Union Algorithms

Robert E. Tarjan, Jan van Leeuwen

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

323 Scopus citations

Abstract

This paper analyzes the asymptotic worst-case running time of a number of variants of the well-known method of path compression for maintaining a collection of disjoint sets under union. We show that two one-pass methods proposed by van Leeuwen and van der Weide are asymptotically optimal, whereas several other methods, including one proposed by Rein and advocated by Dijkstra, are slower than the best methods.

Original language	English (US)
Pages (from-to)	245-281
Number of pages	37
Journal	Journal of the ACM (JACM)
Volume	31
Issue number	2
DOIs	https://doi.org/10.1145/62.2160
State	Published - Mar 30 1984
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Keywords

Equivalence algorithm
inverse Aekermann's function
set union

Access to Document

10.1145/62.2160

Cite this

@article{2b9a1884c19b4dec882e2235557803df,

title = "Worst-Case Analysis of Set Union Algorithms",

abstract = "This paper analyzes the asymptotic worst-case running time of a number of variants of the well-known method of path compression for maintaining a collection of disjoint sets under union. We show that two one-pass methods proposed by van Leeuwen and van der Weide are asymptotically optimal, whereas several other methods, including one proposed by Rein and advocated by Dijkstra, are slower than the best methods.",

keywords = "Equivalence algorithm, inverse Aekermann's function, set union",

author = "Tarjan, {Robert E.} and {van Leeuwen}, Jan",

year = "1984",

month = mar,

day = "30",

doi = "10.1145/62.2160",

language = "English (US)",

volume = "31",

pages = "245--281",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

T1 - Worst-Case Analysis of Set Union Algorithms

AU - Tarjan, Robert E.

AU - van Leeuwen, Jan

PY - 1984/3/30

Y1 - 1984/3/30

N2 - This paper analyzes the asymptotic worst-case running time of a number of variants of the well-known method of path compression for maintaining a collection of disjoint sets under union. We show that two one-pass methods proposed by van Leeuwen and van der Weide are asymptotically optimal, whereas several other methods, including one proposed by Rein and advocated by Dijkstra, are slower than the best methods.

AB - This paper analyzes the asymptotic worst-case running time of a number of variants of the well-known method of path compression for maintaining a collection of disjoint sets under union. We show that two one-pass methods proposed by van Leeuwen and van der Weide are asymptotically optimal, whereas several other methods, including one proposed by Rein and advocated by Dijkstra, are slower than the best methods.

KW - Equivalence algorithm

KW - inverse Aekermann's function

KW - set union

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

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

U2 - 10.1145/62.2160

DO - 10.1145/62.2160

M3 - Article

AN - SCOPUS:0021415472

SN - 0004-5411

VL - 31

SP - 245

EP - 281

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 2

ER -

Worst-Case Analysis of Set Union Algorithms

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this