Asymptotically Ught tune-space trade-offs for pebblmg three different classes of directed aeychc graphs are derived Let N be the size of the graph, S the number of avadable pebbles, and T the time necessary for pebbling the graph A time-space trade-off of the form ST = O(N2) ls proved for pebbhng (usmg only black pebbles) a specml class of permutaaon graphs that tmplement the bR-reversal permutation. If we are allowed to use black and whtte pebblese the time-space trade-off is shown to be of the form T=O(N2/S2 +O(N)) A tune-space trade-off of the form T=SO(N/S)O(N/S) proved for pebbling a class of graphs constructed by stacking superconcentrators m series. This tunespace trade-off holds whether we use only black or black and white pebbles A tune-space trade-off of the form T=S2(N/S)2O(N/S) Is proved for the class of all directed acychc graphs This trade-off also holds whether we use only black or black and white pebbles.
All Science Journal Classification (ASJC) codes
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence
- Lower bounds
- pebble game