Upper and lower bounds on time-space tradeoffs

Thomas Lengauer, Robert Endre Tarjan

Research output: Contribution to journalConference article

21 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)262-277
Number of pages16
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Apr 30 1979
Externally publishedYes
Event11th Annual ACM Symposium on Theory of Computing, STOC 1979 - Atlanta, United States
Duration: Apr 30 1979May 2 1979

All Science Journal Classification (ASJC) codes

  • Software

Cite this