On Reducing the Space Requirements of a Straight-Line Algorithm

DOI10.1137/0605042zbMath0543.68028OpenAlexW2012043526MaRDI QIDQ3332245

David A. Carlson

Publication date: 1984

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0605042

zbMATH Keywords

time-space tradeoffstorage allocationpebble gamestraight-line algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Extreme time-space tradeoffs for graphs with small space requirements
• Time-space trade-offs in a pebble game
• Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
• Asymptotically tight bounds on time-space trade-offs in a pebble game
• Space-time tradeoffs for linear recursion
• On Time Versus Space
• Space bounds for a game on graphs
• Space-time trade-offs on the FFT algorithm
• A Time-Space Trade-Off

This page was built for publication: On Reducing the Space Requirements of a Straight-Line Algorithm