On pointers versus addresses

DOI10.1145/146637.146666MaRDI QIDQ4302806zbMATH OpenOpenAlexFDO

Authors Amir M. Ben-Amram, Zvi Galil

Publication date 21 August 1994

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/146637.146666

zbMATH Keywords

incompressibilitypointer structuresRAMrandom access machinerandom access memory

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On time versus space III
• Hierarchies and space measures for pointer machines
• Lower bounds on algebraic random access machines
• Topological lower bounds on algebraic random access machines

Cited in

(12)

• Unit-cost pointers versus logarithmic-cost addresses
• When can we sort in o(n n) time?
• Sorting, linear time and the satisfiability problem
• Lower bounds for dynamic algebraic problems
• Does indirect addressing matter?
• Hierarchies and space measures for pointer machines
• P-RAM vs. RP-RAM
• On time versus space III
• A nonlinear lower bound for random-access machines under logarithmic cost
• Dynamic normal forms and dynamic characteristic polynomial
• Sequential and parallel algorithms for the NCA problem on pure pointer machines
• Random access machines with multi-dimensional memories

This page was built for publication: On pointers versus addresses

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