On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
From MaRDI portal
Publication:3756517
DOI10.1137/0215072zbMATH Open0619.68039OpenAlexW2067411846MaRDI QIDQ3756517FDOQ3756517
Authors: Norbert Blum 
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215072
Recommendations
- scientific article; zbMATH DE number 3907792
- A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals
- A linear-time algorithm for a special case of disjoint set union
- The complexity of unions of disjoint sets
- The Complexity of Unions of Disjoint Sets
- Worst-case Analysis of Set Union Algorithms
- Worst-case analysis of the set-union problem with extended backtracking
- A randomized concurrent algorithm for disjoint set union
- Worst-case and amortised optimality in union-find (extended abstract)
Cited In (20)
- Worst-case Analysis of Set Union Algorithms
- A randomized concurrent algorithm for disjoint set union
- Complexity of algorithm and operations on trees
- An output sensitive solution to the set union and intersection problem
- On the succinct representation of equivalence classes
- Maintaining bridge-connected and biconnected components on-line
- A linear-time algorithm for a special case of disjoint set union
- Efficient algorithms for the temporal precedence problem
- Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem
- Postorder Disjoint Set Union is Linear
- 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
- Recognizing union-find trees is NP-complete
- Concurrent disjoint set union
- Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract)
- Recognizing union-find trees built up using union-by-rank strategy is NP-complete
- Worst-case and amortised optimality in union-find (extended abstract)
- Intersection reporting on two collections of disjoint sets
- An optimal data structure to handle dynamic environments in non-deterministic computations
This page was built for publication: On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3756517)
