Accession Number:

ADA076264

Title:

Upper and Lower Bounds on Time-Space Tradeoffs in a Pebble Game.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Lengauer,Thomas

Report Date:

1979-07-01

Pagination or Media Count:

83.0

Abstract:

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

Descriptors:

• *GAME THEORY
• GRAPHS
• INTEGER PROGRAMMING
• BOUNDARIES
• ASYMPTOTIC SERIES
• TRADE OFF ANALYSIS
• PERMUTATIONS

Subject Categories:

• Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE