Institution: Stanford University, Department of Computer Science

Title: Time-space trade-offs in a pebble game

Author: Paul, Wolfgang J.

Author: Tarjan, Robert Endre

Date: July 1977

Abstract: A certain pebble game on graphs has been studied in various contexts as a model for the time and space requirements of computations. In this note it is shown that there exists a family of directed acyclic graphs $G_n$ and constants $c_1$, $c_2$, $c_3$ such that (1) $G_n$ has n nodes and each node in $G_n$ has indegree at most 2. (2) Each graph $G_n$ can be pebbled with $c_1\sqrt{n}$ pebbles in n moves. (3) Each graph $G_n$ can also be pebbled with $C_2\sqrt{n}$ pebbles, $c_2$ < $c_1$, but every strategy which achieves this has at least $2^{c_3\sqrt{n}}$ moves.

http://i.stanford.edu/pub/cstr/reports/cs/tr/77/619/CS-TR-77-619.pdf