Upper and Lower Bounds on Time-Space Tradeoffs in a Pebble Game.
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
We derive asymptotically tight time-space tradeoffs for pebbling three different classes of directed acyclic graphs. Let N be the size of the graph, S the number of available pebbles, and T the time necessary for pebbling the graph. A time-space tradeoff of the form STThetaN-squared is proved for pebblingusing only black pebbles a special class of permutation graphs that implement the bit reversal permutation. If we are allowed to use black and white pebbles the time-space tradeoff is shown to be of the form TThetaN-squaredS-squaredThetaN. A time-space tradeoff of the form TS ThetaNS-to the power ThetaNS is proved for pebbling a class of graphs constructed by stacking superconcentrators in series. This time-space tradeoff holds whether we use only black or black and white pebbles. A time-space tradeoff of the form TS 2 to the power 2 to the power ThetaNs is proved for pebbling general directed acyclic graphs with only black or black and white pebbles. Author
- Numerical Mathematics