Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game
Rüdiger Reischuk · Journal of the ACM · 1980
Every family of graphs G. with n nodes and bounded mdegree can be pebbled with o(n) pebbles m time o(n ~+') for all • > 0 There ts a family of graphs G. such that pebbling G. with O(n/logn) pebbles reqmres more than n(logn)* moves for all k.The N-node jellyfish graph can be pebbled with O((IogN) 2) pebbles and O( N ) moves.