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