Space-time tradeoffs for linear recursion

DOI10.1007/BF01744566zbMath0502.68006OpenAlexW2052285161MaRDI QIDQ3968456

Sowmitri Swamy, John E. Savage

Publication date: 1983

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01744566

zbMATH Keywords

pebbling of a simple graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) General topics in the theory of software (68N01)

Related Items

On Reducing the Space Requirements of a Straight-Line Algorithm, Nullstellensatz size-degree trade-offs from reversible pebbling, Nullstellensatz size-degree trade-offs from reversible pebbling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time-space trade-offs in a pebble game
• On Time Versus Space
• Space bounds for a game on graphs
• Space-time trade-offs on the FFT algorithm
• A Time-Space Trade-Off
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game