On Reducing the Space Requirements of a Straight-Line Algorithm

DOI10.1137/0605042MaRDI QIDQ3332245zbMATH OpenOpenAlexFDO

Authors 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

storage allocationtime-space tradeoffpebble gamestraight-line algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Publication:3711762
• Publication:4260386
• Rounds versus time for the two person pebble game (extended abstract)
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Time-space tradeoffs in algebraic complexity theory

Cites work

• scientific article; zbMATH DE number 3521893 (Why is no real title available?)
• scientific article; zbMATH DE number 3614810 (Why is no real title available?)
• scientific article; zbMATH DE number 3628386 (Why is no real title available?)
• A Time-Space Trade-Off
• Asymptotically tight bounds on time-space trade-offs in a pebble game
• Extreme time-space tradeoffs for graphs with small space requirements
• On Time Versus Space
• Space bounds for a game on graphs
• Space-time trade-offs on the FFT algorithm
• Space-time tradeoffs for linear recursion
• Time-space trade-offs in a pebble game
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations

Cited in

(3)

• scientific article; zbMATH DE number 3940742 (Why is no real title available?)
• Space reduction and an extension for a hidden line elimination algorithm
• Topological parameters for time-space tradeoff

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

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