Report Number: CS-TR-78-661
Institution: Stanford University, Department of Computer Science
Title: Variations of a pebble game on graphs
Author: Gilbert, John R.
Author: Tarjan, Robert Endre
Date: September 1978
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.