Upper and Lower Bounds on Time-Space Tradeoffs in a Pebble Game.

Abstract

We derive asymptotically tight 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 time-space tradeoff of the form ST=Theta(N-squared) is proved for pebbling(using only black pebbles) a special class of permutation graphs that implement the bit reversal permutation. If we are allowed to use black and white pebbles the time-space tradeoff is shown to be of the form T=Theta(N-squared/S-squared)+Theta(N). A time-space tradeoff of the form T=S Theta(N/S)-to the power Theta(N/S) is proved for pebbling a class of graphs constructed by stacking superconcentrators in series. This time-space tradeoff holds whether we use only black or black and white pebbles. A time-space tradeoff of the form T=S 2 to the power 2 to the power Theta(N/s) is proved for pebbling general directed acyclic graphs with only black or black and white pebbles. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1979
Accession Number
ADA076264

Entities

People

  • Thomas Lengauer

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Automata Theory
  • Base Lines
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Equations
  • Intervals
  • Language
  • Machines
  • New York
  • Theoretical Computer Science
  • Theses
  • Time Intervals
  • Two Dimensional

Readers

  • Fault Tolerant Diagnosis of Black and White Balloon Isolation Tests Using ¥.
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space