Accession Number:

ADA046481

Title:

Time-Space Trade-offs in a Pebble Game,

Descriptive Note:

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1977-07-01

Pagination or Media Count:

10.0

Abstract:

A certain pebble game on graphs has been studied in various contexts as a model for the time and space requirements of computations. In this note it is shown that there exists a family of directed acyclic graphs Gn and constants c1, c2, c3 such that 1 Gn has n nodes and each node in Gn has indegree at most 2 2 Each graph Gn can be pebbled with c1 sq. rt. n pebbles in n moves and 3 Each graph Gn can also be pebbled with c2 sq. rt. n pebbles, c2 c1, but every strategy which achieves this has at least 2 to the power c3 sq. rt. n moves. Author

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE