Lower bounds for union-split-find related problems on random access machines

DOI10.1145/195058.195415MaRDI QIDQ2817656zbMATHOpenAlexFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• A Lower Bound on the Complexity of the Union-Split-Find Problem
• Lower bounds for the union-find and the split-find problem on pointer machines
• scientific article; zbMATH DE number 4035134
• scientific article; zbMATH DE number 857346
• Lower bounds for dynamic data structures on algebraic RAMs

Cited in

(27)

• Optimal collapsing protocol for multiparty pointer jumping
• ANN for time series under the Fréchet distance
• Cell-probe lower bounds for the partial match problem
• Protocols for asymmetric communication channels
• Sorting and searching revisted
• Predecessor queries in dynamic integer sets
• A Lower Bound on the Complexity of the Union-Split-Find Problem
• Improved fast integer sorting in linear space
• Predecessor on the Ultra-Wide Word RAM
• On the cell probe complexity of polynomial evaluation
• Lower bounds for dynamic data structures on algebraic RAMs
• On the difficulty of range searching
• Fully Dynamic Transitive Closure in plane dags with one source and one sink
• Lower bounds for dynamic transitive closure, planar point location, and parentheses matching
• On data structures and asymmetric communication complexity
• A generalization of a lower bound technique due to Fredman and Saks
• A strong lower bound for approximate nearest neighbor searching
• Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
• On the difficulty of range searching.
• Lower bounds for dynamic algebraic problems
• scientific article; zbMATH DE number 7250167 (Why is no real title available?)
• Neighbours on a grid
• Optimal bounds for the predecessor problem and related problems
• Dynamic nested brackets
• Dynamic algorithms for the Dyck languages
• scientific article; zbMATH DE number 4035134 (Why is no real title available?)
• Lower bounds for predecessor searching in the cell probe model

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)