BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-76-545
       ENTRY:: July 04, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Space bounds for a game on graphs
        TYPE:: Technical Report
      AUTHOR:: Paul, Wolfgang L.
      AUTHOR:: Tarjan, Robert Endre
      AUTHOR:: Celoni, James R.
        DATE:: March 1976
       PAGES:: 22
    ABSTRACT:: We study a one-person game played by placing pebbles,
               according to certain rules, on the vertices of a directed
               graph. In [J. Hopcroft, W. Paul, and L. Valiant, "On time
               versus space and related problems," Proc. 16th Annual Symp.
               on Foundations of Computer Science (1975), pp.57-64] it was
               shown that for each graph with n vertices and maximum
               in-degree d, there is a pebbling strategy which requires at
               most c(d) n/log n pebbles. Here we show that this bound is
               tight to within a constant factor. We also analyze a variety
               of pebbling algorithms, including one which achieves the
               O(n/log n) bound.
       NOTES:: [Adminitrivia V1/Prg/19950704]
         END:: STAN//CS-TR-76-545