scientific article; zbMATH DE number 3907792
From MaRDI portal
Publication:3685219
[For the entire collection see Zbl 0561.00020.] We give an algorithm for the disjoint set union problem, within the class of algorithms defined by Tarjan, which has O(log n/log log n) single- operation time complexity in the worst-case. Also we define a class of algorithms for the disjoint set union problem, which includes the class of algorithms defined by Tarjan. We prove that any algorithm from this class has at least \(\Omega\) (log n/log log n) single-operation time complexity in the worst-case.
Recommendations
- On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
- 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
(13)- A linear-time algorithm for a special case of disjoint set union
- 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
- Average running time analysis of an algorithm to calculate the size of the union of Cartesian products.
- Intersection reporting on two collections of disjoint sets
- Concurrent disjoint set union
- Worst-case and amortised optimality in union-find (extended abstract)
- A partially persistent data structure for the set-union problem
- Postorder Disjoint Set Union is Linear
- On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
- Worst-case Analysis of Set Union Algorithms
- A randomized concurrent algorithm for disjoint set union
- Complexity of algorithm and operations on trees
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3685219)