Worst-case Analysis of Set Union Algorithms

DOI10.1145/62.2160zbMATH Open0632.68043DBLPjournals/jacm/TarjanL84OpenAlexW2044146725WikidataQ56454027 ScholiaQ56454027MaRDI QIDQ3769963FDOQ3769963

Authors: J. Van Leeuwen, Robert E. 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

Recommendations

• scientific article; zbMATH DE number 3907792
• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
• Probabilistic Analysis of Disjoint Set Union Algorithms
• A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals
• Top-Down Analysis of Path Compression

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)

Cited In (88)

• A randomized concurrent algorithm for disjoint set union
• Finding paths and deleting edges in directed acyclic graphs
• Disjoint set union with randomized linking
• The fuzzy association degree in semantic data models
• Finding dominators via disjoint set union
• Complexity of algorithm and operations on trees
• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
• Fast connected-component labeling
• Confluence modulo equivalence in Constraint Handling Rules
• Quasi-Linear-Time Algorithms by Generalisation of Union-Find in CHR
• Unifications, deunifications, and their complexity
• A fuzzy approach to classification of text documents
• Efficient fully-compressed sequence representations
• Average running time analysis of an algorithm to calculate the size of the union of Cartesian products.
• A simple and efficient union-find-delete algorithm
• A tight lower bound for top-down skew heaps
• Maintaining bridge-connected and biconnected components on-line
• Analysis of the total costs for variants of the union-find algorithm
• A tight amortized bound for path reversal
• On the Expected Performance of Path Compression Algorithms
• A linear-time algorithm for a special case of disjoint set union
• Polytopes associated with symmetry handling
• A data structure for dynamic trees
• The grammatical inference problem for the Szilard languages of linear grammars
• Range minimum queries in minimal space
• Average case analysis of fully dynamic reachability for directed graphs
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Fuzzy functional dependencies and Bayesian networks
• Machine-checked verification of the correctness and amortized complexity of an efficient union-find implementation
• Automatically finding clusters in normalized cuts
• Computing the vertices of tropical polyhedra using directed hypergraphs
• An optimal algorithm for generating minimal perfect hash functions
• The fuzzy functional dependency on the basis of the semantic distance
• ALGORITHMS FOR K-DISJOINT MAXIMUM SUBARRAYS
• A practical unification algorithm
• Worst-case analysis of the set-union problem with extended backtracking
• Title not available (Why is that?)
• A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals
• Combinatorial-topological framework for the analysis of global dynamics
• Amortized Analysis of Algorithms for Set Union with Backtracking
• Probabilistic Analysis of Disjoint Set Union Algorithms
• The nearest common ancestor in a dynamic tree
• Amortized efficiency of a path retrieval data structure
• A partially persistent data structure for the set-union problem
• On the structural grammatical inference problem for some classes of context-free grammars
• Maintenance of 2- and 3-edge-connected components of graphs. I
• Top-Down Analysis of Path Compression
• On proving confluence modulo equivalence for Constraint Handling Rules
• The recognition of union trees
• The set union problem with dynamic weighted backtracking
• Intersection reporting on two collections of disjoint sets
• Perfect hashing
• Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits
• Size functions for comparing 3D models
• Primitives for asynchronous list compression
• Two linear time Union--Find strategies for image processing
• Multidimensional cell lists for investigating 3-manifolds
• Identification of function distinguishable languages.
• Amortized Computational Complexity
• Constraint and satisfiability reasoning for graph coloring
• A note on set union with arbitrary deunions
• Depth First Search in the Semi-streaming Model
• Lower bound framework for differentially private and oblivious data structures
• Lexicographic optimal homologous chains and applications to point cloud triangulations
• An output sensitive solution to the set union and intersection problem
• Inferring regular languages by merging nonterminals
• Integer Programming Formulations for Minimum Spanning Tree Interdiction
• FLUID: a common model for semantic structural graph summaries based on equivalence relations
• Comparative study and proof of single-pass connected components algorithms
• An asymptotic study for path reversal.
• Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
• Online adaptive basis refinement and compression for reduced-order models via vector-space sieving
• Dynamic Euclidean bottleneck matching
• Memory management for union-find algorithms
• Relation-algebraic verification of disjoint-set forests
• Lightweight shape analysis based on physical types
• Title not available (Why is that?)
• Linear time algorithms for two disjoint paths problems on directed acyclic graphs
• Algebraic Bayesian networks: checking backbone connectivity
• Parallelism, concurrency and distribution in constraint handling rules: a survey
• Fast approximation algorithm for maximum lifetime aggregation trees in wireless sensor networks
• Concurrent disjoint set union
• Conjugacy search problem and the Andrews-Curtis conjecture
• On efficient algorithms for bottleneck path problems with many sources
• Worst-case and amortised optimality in union-find (extended abstract)
• A BWT-based algorithm for random de Bruijn sequence construction
• Average case analysis of fully dynamic connectivity for directed graphs
• Automata, Languages and Programming

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3769963)