Asymptotically Tight Bounds on Time-Space Trade-Offs in a Pebble Game

Thomas Lengauer, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

61 Scopus citations

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 languageEnglish (US)
Pages (from-to)1087-1130
Number of pages44
JournalJournal of the ACM (JACM)
Volume29
Issue number4
DOIs
StatePublished - Oct 1 1982
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Lower bounds
  • pebble game
  • superconcentrators

Fingerprint

Dive into the research topics of 'Asymptotically Tight Bounds on Time-Space Trade-Offs in a Pebble Game'. Together they form a unique fingerprint.

Cite this