Lower bounds for dynamic data structures on algebraic RAMs

DOI10.1007/S00453-001-0079-6zbMATH Open1050.68025OpenAlexW2012620452MaRDI QIDQ1348938FDOQ1348938

Authors: Amir M. Ben-Amram, Zvi Galil 

Publication date: 21 May 2002

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-001-0079-6

Recommendations

• A generalization of a lower bound technique due to Fredman and Saks
• Tight bounds for the partial-sums problem
• Lower bounds for union-split-find related problems on random access machines
• Logarithmic Lower Bounds in the Cell-Probe Model
• Lower bounds on algebraic random access machines

zbMATH Keywords

random access machinecell-probe lower boundsdynamic prefix sumOutput Variability

Mathematics Subject Classification ID

Data structures (68P05)

Cited In (10)

• A generalization of a lower bound technique due to Fredman and Saks
• Static data structure lower bounds imply rigidity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds for union-split-find related problems on random access machines
• Invariance properties of RAMs and linear time
• Partial sums on the ultra-wide word RAM
• Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
• Title not available (Why is that?)
• Lower bounds for dynamic algebraic problems

This page was built for publication: Lower bounds for dynamic data structures on algebraic RAMs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1348938)