Lower bounds for dynamic algorithms

DOI10.1007/3-540-58218-5_15zbMath1502.68130OpenAlexW1565705576MaRDI QIDQ5056175

Michael L. Fredman

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58218-5_15

zbMATH Keywords

cell probe model of computation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topics in the theory of algorithms (68W01) Other nonclassical models of computation (68Q09)

Cites Work

• A lower bound for finding predecessors in Yao's cell probe model
• Surpassing the information theoretic bound with fusion trees
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Improved data structures for fully dynamic biconnectivity
• Should Tables Be Sorted?
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Design and implementation of an efficient priority queue
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower bounds for dynamic algorithms