Time-space trade-offs in a pebble game

DOI10.1007/BF00289150zbMath0399.05030OpenAlexW2063264061MaRDI QIDQ1254254

Wolfgang J. Paul, Robert Endre Tarjan

Publication date: 1978

Published in: Acta Informatica (Search for Journal in Brave)

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

zbMATH Keywords

ComplexityGraphsDirected Acyclic GraphsOne Person GamePebBle Game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Game theory (91A99) Directed graphs (digraphs), tournaments (05C20) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items

Space-time tradeoffs for linear recursion, Proof of Space from Stacked Expanders, Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks, A time-space tradeoff for sorting on non-oblivious machines, On uniform circuit complexity, Pebbling with an auxiliary pushdown, Extreme time-space tradeoffs for graphs with small space requirements, Time-space tradeoffs for algebraic problems on general sequential machines, Time-space tradeoffs in algebraic complexity theory, On Reducing the Space Requirements of a Straight-Line Algorithm, Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space

Cites Work

• On the complexity of an optimal non-blocking commutation scheme without reorganization
• Complete Register Allocation Problems
• On Time Versus Space
• Superconcentrators
• Space bounds for a game on graphs
• A Time-Space Trade-Off
• Unnamed Item
• Unnamed Item