Efficiency of a Good But Not Linear Set Union Algorithm

1975/04/01 by Robert E. Tarjan, Robert Endre Tarjan · 21 citations
Medicine · #Respiratory Support and Mechanisms #Respiratory Support and Mechanisms #Obstructive Sleep Apnea Research

paper · pdf · doi:10.1145/321879.321884

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
• 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