Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game (preliminary version)
Rüdiger Reischuk · Foundations of Computer Science · 1978
Every family of graphs G n with n nodes and bounded in-degree can be pebbled with o(n) pebbles in time 0(n 1 + c ) for all c>O. There is a family of graphs G such that pebbling G with O(n/log n) n n k pebbles requires w(n(log n) ) moves for all k. The n-node jellyfish-graph as defined in (1) can be pebbled with O«log n)2) pebbles and O(n) moves.