Time-space trade-offs in a pebble game

Research output: Contribution to journalArticle

19 Scopus citations

Abstract

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 2c 3√n moves.

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

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications

Cite this