Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 1087-1130 |
Number of pages | 44 |
Journal | Journal of the ACM (JACM) |
Volume | 29 |
Issue number | 4 |
DOIs | |
State | Published - Oct 1 1982 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence
Keywords
- Lower bounds
- pebble game
- superconcentrators