TY - JOUR

T1 - Upper and lower bounds on time-space tradeoffs

AU - Lengauer, Thomas

AU - Tarjan, Robert Endre

N1 - Funding Information:
-~/ Research partly supported by a Guggenheim Fellowship, by National Science Foundation g grant MCS75-22870 and by Office of Naval Research contract N00014-76-C-0688. Reproduc-tion in whole or in part is permitted for any purpose of the United States government.
Funding Information:
Research supported by the German Academic Exchange Service.

PY - 1979/4/30

Y1 - 1979/4/30

N2 - This paper derives asymptotically tight hounds on the time-space tradeoffs for pebbling tnree 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) A time space tradeoff of the form ST = 9(N2) is proved for a special class of permutation graphs which implement the bit reversal permutation. (b) A time-space tradeoff of the form T = s e(N/s)8N/s is proved for a class of graphs constructed by stacking superconcentrators in series. (c) A time-space tradeoff of the form 2e(w/s) T = S-2 is proved for pebbling general directed acyclic graphs.

AB - This paper derives asymptotically tight hounds on the time-space tradeoffs for pebbling tnree 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) A time space tradeoff of the form ST = 9(N2) is proved for a special class of permutation graphs which implement the bit reversal permutation. (b) A time-space tradeoff of the form T = s e(N/s)8N/s is proved for a class of graphs constructed by stacking superconcentrators in series. (c) A time-space tradeoff of the form 2e(w/s) T = S-2 is proved for pebbling general directed acyclic graphs.

UR - http://www.scopus.com/inward/record.url?scp=0005259318&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0005259318&partnerID=8YFLogxK

U2 - 10.1145/800135.804420

DO - 10.1145/800135.804420

M3 - Conference article

AN - SCOPUS:0005259318

SN - 0737-8017

SP - 262

EP - 277

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 11th Annual ACM Symposium on Theory of Computing, STOC 1979

Y2 - 30 April 1979 through 2 May 1979

ER -