Time-Space Trade-offs in a Pebble Game,
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 G(n) and constants c(1), c(2), c(3) such that (1) G(n) has n nodes and each node in G(n) has indegree at most 2; (2) Each graph G(n) can be pebbled with c(1) sq. rt. n pebbles in n moves; and (3) Each graph G(n) can also be pebbled with c(2) sq. rt. n pebbles, c(2) < c(1), but every strategy which achieves this has at least 2 to the power (c(3) sq. rt. n ) moves. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1977
- Accession Number
- ADA046481
Entities
People
- R. E. Tarjan
- W. J. Paul
Organizations
- Stanford University