Improved bounds on the problem of time-space trade-off in the pebble game

1 October 1978

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02725428,p. 84-91
https://doi.org/10.1109/sfcs.1978.19

Abstract

Every family of graphs Gn with n nodes and bounded in-degree can be pebbled with o(n) pebbles in time o(n 1+c) for all c≫0. There is a family of graphs Gn such that pebbling Gn with O(n/log n) pebbles requires ω(n(log n)k) 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.

Keywords

UPPER BOUND

This publication has 3 references indexed in Scilit:

Time-space tradeoffs for computing functions, using connectivity properties of their circuits
Published by Association for Computing Machinery (ACM) ,1978
On Time Versus Space
Journal of the ACM, 1977
An observation on time-storage trade off
Published by Association for Computing Machinery (ACM) ,1973