We study a one-person game played by placing pebbles, according to certain rules, on the vertices of a directed graph. In  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 0(n/log n) bound.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computational Theory and Mathematics
- Pebble game
- Register allocation
- Space bounds
- Turing machines