Worst-case Analysis of Set Union Algorithms

DOI10.1145/62.2160zbMath0632.68043DBLPjournals/jacm/TarjanL84OpenAlexW2044146725WikidataQ56454027 ScholiaQ56454027MaRDI QIDQ3769963

Jan van Leeuwen, Robert Endre Tarjan

Publication date: 1984

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/62.2160

zbMATH Keywords

inverse Ackermann functionset unionpath compressionasymptotic worst-case running timeequivalence algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99)

Related Items (71)

An asymptotic study for path reversal. ⋮ A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals ⋮ The recognition of union trees ⋮ A tight lower bound for top-down skew heaps ⋮ Efficient algorithms for finding minimum spanning trees in undirected and directed graphs ⋮ Memory management for Union-Find algorithms ⋮ Amortized efficiency of a path retrieval data structure ⋮ Quasi-Linear-Time Algorithms by Generalisation of Union-Find in CHR ⋮ Lightweight shape analysis based on physical types ⋮ Amortized Computational Complexity ⋮ Parallelism, concurrency and distribution in constraint handling rules: A survey ⋮ Finding paths and deleting edges in directed acyclic graphs ⋮ A partially persistent data structure for the set-union problem ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ Worst-case analysis of the set-union problem with extended backtracking ⋮ Online adaptive basis refinement and compression for reduced-order models via vector-space sieving ⋮ Combinatorial-topological framework for the analysis of global dynamics ⋮ Machine-Checked Verification of the Correctness and Amortized Complexity of an Efficient Union-Find Implementation ⋮ Primitives for asynchronous list compression ⋮ Linear time algorithms for two disjoint paths problems on directed acyclic graphs ⋮ Polytopes associated with symmetry handling ⋮ Perfect hashing ⋮ Finding dominators via disjoint set union ⋮ Confluence Modulo Equivalence in Constraint Handling Rules ⋮ A simple and efficient union-find-delete algorithm ⋮ Fuzzy functional dependencies and Bayesian networks ⋮ Identification of function distinguishable languages. ⋮ Lower bound framework for differentially private and oblivious data structures ⋮ Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements ⋮ Computing the vertices of tropical polyhedra using directed hypergraphs ⋮ Average case analysis of fully dynamic connectivity for directed graphs ⋮ A fuzzy approach to classification of text documents ⋮ Unnamed Item ⋮ The grammatical inference problem for the Szilard languages of linear grammars ⋮ Constraint and Satisfiability Reasoning for Graph Coloring ⋮ FLUID: a common model for semantic structural graph summaries based on equivalence relations ⋮ Unifications, deunifications, and their complexity ⋮ Efficient fully-compressed sequence representations ⋮ Size functions for comparing 3D models ⋮ Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits ⋮ Maintaining bridge-connected and biconnected components on-line ⋮ Two linear time Union--Find strategies for image processing ⋮ On proving confluence modulo equivalence for Constraint Handling Rules ⋮ On the structural grammatical inference problem for some classes of context-free grammars ⋮ Maintenance of 2- and 3-edge-connected components of graphs. I ⋮ An optimal algorithm for generating minimal perfect hash functions ⋮ Complexity of algorithm and operations on trees ⋮ Fast connected-component labeling ⋮ The fuzzy association degree in semantic data models ⋮ Automatically finding clusters in normalized cuts ⋮ Algebraic Bayesian networks: checking backbone connectivity ⋮ A note on set union with arbitrary deunions ⋮ A practical unification algorithm ⋮ Conjugacy search problem and the Andrews-Curtis conjecture ⋮ Depth First Search in the Semi-streaming Model ⋮ Intersection reporting on two collections of disjoint sets ⋮ Concurrent disjoint set union ⋮ The nearest common ancestor in a dynamic tree ⋮ Fast Approximation Algorithm for Maximum Lifetime Aggregation Trees in Wireless Sensor Networks ⋮ A tight amortized bound for path reversal ⋮ Range minimum queries in minimal space ⋮ A data structure for dynamic trees ⋮ Comparative study and proof of single-pass connected components algorithms ⋮ Average case analysis of fully dynamic reachability for directed graphs ⋮ ALGORITHMS FOR K-DISJOINT MAXIMUM SUBARRAYS ⋮ A linear-time algorithm for a special case of disjoint set union ⋮ Lexicographic optimal homologous chains and applications to point cloud triangulations ⋮ The set union problem with dynamic weighted backtracking ⋮ Multidimensional cell lists for investigating 3-manifolds ⋮ The fuzzy functional dependency on the basis of the semantic distance ⋮ Inferring regular languages by merging nonterminals

This page was built for publication: Worst-case Analysis of Set Union Algorithms