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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/78/661/CS-TR-78-661.pdf