Efficiency of a Good But Not Linear Set Union Algorithm

Research output: Contribution to journalArticle

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

Original languageEnglish (US)
Pages (from-to)215-225
Number of pages11
JournalJournal of the ACM (JACM)
Volume22
Issue number2
DOIs
StatePublished - Apr 1 1975
Externally publishedYes

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

Fingerprint Dive into the research topics of 'Efficiency of a Good But Not Linear Set Union Algorithm'. Together they form a unique fingerprint.

  • Cite this