Rounds versus time for the two person pebble game

DOI10.1016/0890-5401(90)90002-YMaRDI QIDQ2641235zbMATH OpenFDO

Authors Bala Kalyanasundaram, Georg Schnitger

Publication date 1990

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

Full work available at URL https://doi.org/10.1016/0890-5401(90)90002-Y

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Recommendations

• Rounds versus time for the two person pebble game (extended abstract)
• scientific article; zbMATH DE number 1333612
• scientific article; zbMATH DE number 3976363
• Reversible pebble game on trees
• On the power of white pebbles

Cites work

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

Cited in

(5)

• Speedup of determinism by alternation for multidimensional Turing machines
• Reversible pebble game on trees
• scientific article; zbMATH DE number 3976363 (Why is no real title available?)
• scientific article; zbMATH DE number 1333612 (Why is no real title available?)
• Rounds versus time for the two person pebble game (extended abstract)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2641235)