Space bounds for a game on graphs

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

Research output: Contribution to journalConference article

20 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 O(n/log n) bound.

Original languageEnglish (US)
Pages (from-to)149-160
Number of pages12
JournalProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F130841
DOIs
StatePublished - May 3 1976
Externally publishedYes
Event8th Annual ACM Symposium on Theory of Computing, STOC 1976 - Hershey, United States
Duration: May 3 1976May 5 1976

All Science Journal Classification (ASJC) codes

  • Software

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