DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA076264
Title:
Upper and Lower Bounds on Time-Space Tradeoffs in a Pebble Game.
Corporate Author:
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Report Date:
1979-07-01
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
Descriptive Note:
Technical rept.,
Pages:
0083
Contract Number:
N00014-76-C-0688
File Size:
31.82MB
