Lower bounds for union-split-find related problems on random access machines
DOI10.1145/195058.195415zbMATH Open1345.68118OpenAlexW2050108834MaRDI QIDQ2817656FDOQ2817656
Authors: Peter Bro Miltersen 
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/60938/7/WRAP_cs-rr-258.pdf
Recommendations
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Cited In (27)
- Title not available (Why is that?)
- A generalization of a lower bound technique due to Fredman and Saks
- Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
- Cell-probe lower bounds for the partial match problem
- A strong lower bound for approximate nearest neighbor searching
- Dynamic nested brackets
- ANN for time series under the Fréchet distance
- A Lower Bound on the Complexity of the Union-Split-Find Problem
- Improved fast integer sorting in linear space
- On the difficulty of range searching
- On the difficulty of range searching.
- Title not available (Why is that?)
- Lower bounds for dynamic data structures on algebraic RAMs
- Lower bounds for predecessor searching in the cell probe model
- Predecessor on the Ultra-Wide Word RAM
- Lower bounds for dynamic transitive closure, planar point location, and parentheses matching
- Optimal collapsing protocol for multiparty pointer jumping
- Predecessor queries in dynamic integer sets
- Neighbours on a grid
- Optimal bounds for the predecessor problem and related problems
- Fully Dynamic Transitive Closure in plane dags with one source and one sink
- Dynamic algorithms for the Dyck languages
- Protocols for asymmetric communication channels
- On data structures and asymmetric communication complexity
- Lower bounds for dynamic algebraic problems
- Sorting and searching revisted
- On the cell probe complexity of polynomial evaluation
This page was built for publication: Lower bounds for union-split-find related problems on random access machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817656)
