Efficiency of a Good But Not Linear Set Union Algorithm

1975/04/01 by Robert E. Tarjan, Robert Endre Tarjan · 38 citations
Mathematics · Medicine · #Algorithm #Computer science #Mathematics #Obstructive Sleep Apnea Research #Respiratory Support and Mechanisms #Set (abstract data type)

paper · pdf · doi:10.1145/321879.321884

published in Journal of the ACM 22(2), 215-225 (Association for Computing Machinery)

openalex publication_date 1975/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/21

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) < k:ma(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.

Cited by

• Strongly-connected percolation on directed lattices
• Limits of combinatorial patchworking
• Persistent Multiscale Density-based Clustering
• Capacity-Achieving Codes with Inverse-Ackermann-Depth Encoders
• Surrogate Graph Partitioning for Spatial Prediction
• Design of a Quantum Error Correction Decoder Exploiting Temporal Parallelism
• Fast Computation of k-Runs, Parameterized Squares, and Other Generalised Squares
• A Quantum Walk-Driven Algorithm for the Minimum Spanning Tree Problem under a Maximal Degree Constraint
• Harnessing Adaptive Topology Representations for Zero-Shot Graph Question Answering
• AG²aussian: Anchor-Graph Structured Gaussian Splatting for Instance-Level 3D Scene Understanding and Editing
• Multi-Granular Spatio-Temporal Token Merging for Training-Free Acceleration of Video LLMs
• On Propositional Program Equivalence (extended abstract)
• Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut
• Union-Intersection Union-Find for Decoding Depolarizing Errors in Topological Codes
• E-Graphs as a Persistent Compiler Abstraction
• Simplified and Verified: A Second Look at a Proof-Producing Union-Find Algorithm
• Ultra-fast sequence clustering from similarity networks with SiLiX. [europepmc]
• Aligning the unalignable: bacteriophage whole genome alignments. [europepmc]
• CellECT: cell evolution capturing tool. [europepmc]
• Improved collective influence of finding most influential nodes based on disjoint-set reinsertion. [europepmc]
• Investigating the Correspondence of Clinical Diagnostic Grouping With Underlying Neurobiological and Phenotypic Clusters Using Unsupervised Machine Learning. [europepmc]
• Modeling Electrical Percolation to optimize the Electromechanical Properties of CNT/Polymer Composites in Highly Stretchable Fiber Strain Sensors. [europepmc]
• Faster Cut Sparsification of Weighted Graphs. [europepmc]
• Deep learning for automated mandibular canal segmentation in CBCT scans. [europepmc]

Related

• Optimizing diversity
• Fast evaluation of union-intersection expressions
• Computing a many-to-many matching with demands and capacities between two sets using the Hungarian algorithm
• Concurrent Disjoint Set Union
• A Randomized Concurrent Algorithm for Disjoint Set Union