A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals
From MaRDI portal
Publication:1332777
DOI10.1016/0020-0190(94)00082-4zbMath0822.68047OpenAlexW2040370298MaRDI QIDQ1332777
Publication date: 5 September 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)00082-4
Cites Work
- A class of algorithms which require nonlinear time to maintain disjoint sets
- A linear-time algorithm for a special case of disjoint set union
- A complement to Tarjan's result about the lower bound on the complexity of the set union problem
- Lower bounds for the union-find and the split-find problem on pointer machines
- On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
- Worst-case Analysis of Set Union Algorithms
- A Lower Bound on the Complexity of the Union-Split-Find Problem
This page was built for publication: A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals