Efficiency of a Good But Not Linear Set Union Algorithm

Robert Endre Tarjan

doi:10.1145/321879.321884

Efficiency of a Good But Not Linear Set Union Algorithm

Robert Endre Tarjan

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

948 Scopus citations

Abstract

TWO types of instructmns for mampulating a family of disjoint sets which partitmn a umverse of n elements are considered FIND(x) computes the name of the (unique) set containing element x UNION(A, B, C) combines sets A and B into a new set named C. A known algorithm for implementing sequences of these mstructmns is examined It is shown that, if t(m, n) as the maximum time reqmred by a sequence of m ≥ n FINDs and n — 1 intermixed UNIONs, then k_ima(m, n) ≤ t(m, n) ≤ k₂ma(m, n) for some positive constants k_i and k₂, where a(m, n) is related to a functional inverse of Ackermann's functmn and as very slow-growing.

Original language	English (US)
Pages (from-to)	215-225
Number of pages	11
Journal	Journal of the ACM (JACM)
Volume	22
Issue number	2
DOIs	https://doi.org/10.1145/321879.321884
State	Published - Apr 1 1975
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Keywords

algorithm
complexity
eqmvalence
partition
set umon
tree

Access to Document

10.1145/321879.321884

Cite this

@article{6bee13c277dc438890af00b1f021fac5,

title = "Efficiency of a Good But Not Linear Set Union Algorithm",

abstract = "TWO types of instructmns for mampulating a family of disjoint sets which partitmn a umverse of n elements are considered FIND(x) computes the name of the (unique) set containing element x UNION(A, B, C) combines sets A and B into a new set named C. A known algorithm for implementing sequences of these mstructmns is examined It is shown that, if t(m, n) as the maximum time reqmred by a sequence of m ≥ n FINDs and n — 1 intermixed UNIONs, then kima(m, n) ≤ t(m, n) ≤ k2ma(m, n) for some positive constants ki and k2, where a(m, n) is related to a functional inverse of Ackermann's functmn and as very slow-growing.",

keywords = "algorithm, complexity, eqmvalence, partition, set umon, tree",

author = "Tarjan, {Robert Endre}",

year = "1975",

month = apr,

day = "1",

doi = "10.1145/321879.321884",

language = "English (US)",

volume = "22",

pages = "215--225",

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

issn = "0004-5411",

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

number = "2",

}

TY - JOUR

T1 - Efficiency of a Good But Not Linear Set Union Algorithm

AU - Tarjan, Robert Endre

PY - 1975/4/1

Y1 - 1975/4/1

N2 - TWO types of instructmns for mampulating a family of disjoint sets which partitmn a umverse of n elements are considered FIND(x) computes the name of the (unique) set containing element x UNION(A, B, C) combines sets A and B into a new set named C. A known algorithm for implementing sequences of these mstructmns is examined It is shown that, if t(m, n) as the maximum time reqmred by a sequence of m ≥ n FINDs and n — 1 intermixed UNIONs, then kima(m, n) ≤ t(m, n) ≤ k2ma(m, n) for some positive constants ki and k2, where a(m, n) is related to a functional inverse of Ackermann's functmn and as very slow-growing.

AB - TWO types of instructmns for mampulating a family of disjoint sets which partitmn a umverse of n elements are considered FIND(x) computes the name of the (unique) set containing element x UNION(A, B, C) combines sets A and B into a new set named C. A known algorithm for implementing sequences of these mstructmns is examined It is shown that, if t(m, n) as the maximum time reqmred by a sequence of m ≥ n FINDs and n — 1 intermixed UNIONs, then kima(m, n) ≤ t(m, n) ≤ k2ma(m, n) for some positive constants ki and k2, where a(m, n) is related to a functional inverse of Ackermann's functmn and as very slow-growing.

KW - algorithm

KW - complexity

KW - eqmvalence

KW - partition

KW - set umon

KW - tree

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

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

U2 - 10.1145/321879.321884

DO - 10.1145/321879.321884

M3 - Article

AN - SCOPUS:0016495233

SN - 0004-5411

VL - 22

SP - 215

EP - 225

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 2

ER -

Efficiency of a Good But Not Linear Set Union Algorithm

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this