Time-space trade-offs in a pebble game

W. J. Paul, R. E. Tarjan

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


A certain pebble game on graphs has been studied in various contexts as a model for the time and space requirements of computations [1,2,3,8]. 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√n pebbles in n moves. (3) Each graph Gn can also be pebbled with c2√n pebbles, c2<c1, but every strategy which achieves this has at least 2c3√n moves.

Original languageEnglish (US)
Pages (from-to)111-115
Number of pages5
JournalActa Informatica
Issue number2
StatePublished - Jun 1978
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications

Cite this