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

DOI10.1145/195058.195415MaRDI QIDQ2817656zbMATH OpenOpenAlexFDO

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

Data structures (68P05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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

(30)

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

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)