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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/76/545/CS-TR-76-545.pdf