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 -