Space bounds for a game on graphs

DOI10.1007/BF01683275zbMath0366.90150OpenAlexW2077054189MaRDI QIDQ4143082

Wolfgang J. Paul, James R. Celoni, Robert Endre Tarjan

Publication date: 1977

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

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

Mathematics Subject Classification ID

Game theory (91A99) Directed graphs (digraphs), tournaments (05C20) Algorithms in computer science (68W99)

Related Items (33)

Space-time tradeoffs for linear recursion ⋮ On the complexity of resolution with bounded conjunctions ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Smaller superconcentrators of density 28 ⋮ Proof of Space from Stacked Expanders ⋮ Rounds versus time for the two person pebble game ⋮ Revisiting AES-GCM-SIV: multi-user security, faster key derivation, and better bounds ⋮ Eigenvalues and expanders ⋮ Adaptively secure garbling schemes for parallel computations ⋮ On time hierarchies ⋮ Regular and General Resolution: An Improved Separation ⋮ Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks ⋮ A note on the pebble game ⋮ The space complexity of pebble games on trees ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ A comparison of two variations of a pebble game on graphs ⋮ The size and depth of layered Boolean circuits ⋮ Pebbling with an auxiliary pushdown ⋮ Pebble games for studying storage sharing ⋮ The depth of resolution proofs ⋮ Extreme time-space tradeoffs for graphs with small space requirements ⋮ Incremental branching programs ⋮ Construction of expanders and superconcentrators using Kolmogorov complexity ⋮ On Reducing the Space Requirements of a Straight-Line Algorithm ⋮ Highly symmetric expanders ⋮ Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory ⋮ Time-space trade-offs in a pebble game ⋮ Tight time-space lower bounds for finding multiple collision pairs and their applications ⋮ Proofs of Catalytic Space ⋮ A view of computability on term algebras ⋮ Data structures for distributed counting ⋮ Rounds versus time for the two person pebble game ⋮ Speedups of deterministic machines by synchronous parallel machines

Cites Work

• On sparse graphs with dense long paths
• Tape bounds for time-bounded Turing machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Space bounds for a game on graphs