Report Number: CS-TR-76-545
Institution: Stanford University, Department of Computer Science
Title: Space bounds for a game on graphs
Author: Paul, Wolfgang L.
Author: Tarjan, Robert Endre
Author: Celoni, James R.
Date: March 1976
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.