BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-77-619
       ENTRY:: June 28, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Time-space trade-offs in a pebble game
        TYPE:: Technical Report
      AUTHOR:: Paul, Wolfgang J.
      AUTHOR:: Tarjan, Robert Endre
        DATE:: July 1977
       PAGES:: 10
    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.
       NOTES:: [Adminitrivia V1/Prg/19950628]
         END:: STAN//CS-TR-77-619