Extreme time-space tradeoffs for graphs with small space requirements

DOI10.1016/0020-0190(82)90020-5zbMath0503.68049OpenAlexW2040082402MaRDI QIDQ1173412

John E. Savage, David A. Carlson

Publication date: 1982

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(82)90020-5

zbMATH Keywords

directed acyclic graphtime-space tradeoffcomplexity theorypebble game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items

On Reducing the Space Requirements of a Straight-Line Algorithm, Reversible pebble games and the relation between tree-like and general resolution space, 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
• Size-space tradeoffs for oblivious computations
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• 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
• Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game