Report Number: CS-TR-77-619
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.