Space bounds for a game on graphs

Wolfgang J. Paul, Robert Endre Tarjan, James R. Celoni

Research output: Contribution to journalArticlepeer-review

76 Scopus citations

Abstract

We study a one-person game played by placing pebbles, according to certain rules, on the vertices of a directed graph. In [3] it was shown that for each graph with n vertices and maximum in-degree d, there is a pebbling strategy which requires at most c(d) n/log n pebbles. Here we show that this bound is tight to within a constant factor. We also analyze a variety of pebbling algorithms, including one which achieves the 0(n/log n) bound.

Original languageEnglish (US)
Pages (from-to)239-251
Number of pages13
JournalMathematical Systems Theory
Volume10
Issue number1
DOIs
StatePublished - Dec 1 1976
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics

Keywords

  • Pebble game
  • Register allocation
  • Space bounds
  • Turing machines

Fingerprint Dive into the research topics of 'Space bounds for a game on graphs'. Together they form a unique fingerprint.

Cite this