BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-78-661
       ENTRY:: June 22, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Variations of a pebble game on graphs
        TYPE:: Technical Report
      AUTHOR:: Gilbert, John R.
      AUTHOR:: Tarjan, Robert Endre
        DATE:: September 1978
       PAGES:: 26
    ABSTRACT:: We examine two variations of a one-person pebble game played
               on directed graphs, which has been studied as a model of
               register allocation. The black-white pebble game of Cook and
               Sethi is shown to require as many pebbles in the worst case
               as the normal pebble game, to within a constant factor. For
               another version of the pebble game, the problem of deciding
               whether a given number of pebbles is sufficient for a given
               graph is shown to be complete in polynomial space.
       NOTES:: [Adminitrivia V1/Prg/19950622]
         END:: STAN//CS-TR-78-661