Rounds versus time for the two person pebble game

DOI10.1016/0890-5401(90)90002-YzbMATH Open0721.90096MaRDI QIDQ2641235FDOQ2641235

Authors: Bala Kalyanasundaram, Georg Schnitger 

Publication date: 1990

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

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

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)

Cites Work

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

Cited In (4)

• Rounds versus time for the two person pebble game (extended abstract)
• Reversible pebble game on trees
• Speedup of determinism by alternation for multidimensional Turing machines
• Title not available (Why is that?)

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)