upper and lower bounds on time-space tradeoffs
This paper derives asymptotically tight bounds on the 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) A time space tradeoff of the form ST &equil; &thgr;(N 2 ) is proved for a special class of permutation graphs which implement the bit reversal permutation. (b) A time-space tradeoff of the form T &equil; S &thgr;(N/S) &thgr;(N/S) is proved for a class of graphs constructed by stacking superconcentrators in series. (c) A time-space tradeoff of the form T &equil; S.2 2 &thgr;(N/S) is proved for pebbling general directed acyclic graphs.
lower bound timing paper pebble class direct graph size space permutation stack general