Rounds versus time for the two person pebble game

DOI10.1016/0890-5401(90)90002-YzbMath0721.90096MaRDI QIDQ2641235

Georg Schnitger, Bala Kalyanasundaram

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

directed acyclic graphrounds/time tradeoffssize/depth tradeofftwo-person pebble game

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Speedup of determinism by alternation for multidimensional Turing machines

Cites Work

• A universal prior for integers and estimation by minimum description length
• Speedups of deterministic machines by synchronous parallel machines
• On uniform circuit complexity
• Computing multivariate polynomials in parallel
• On sparse graphs with dense long paths
• Circuit size is nonlinear in depth
• Asymptotically tight bounds on time-space trade-offs in a pebble game
• On Time Versus Space
• Superconcentrators
• Space bounds for a game on graphs

This page was built for publication: Rounds versus time for the two person pebble game