Space bounds for a game on graphs

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

doi:10.1145/800113.803643

Space bounds for a game on graphs

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

Research output: Contribution to journal › Conference article › peer-review

24 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 language	English (US)
Pages (from-to)	149-160
Number of pages	12
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	Part F130841
DOIs	https://doi.org/10.1145/800113.803643
State	Published - May 3 1976
Externally published	Yes
Event	8th Annual ACM Symposium on Theory of Computing, STOC 1976 - Hershey, United States Duration: May 3 1976 → May 5 1976

All Science Journal Classification (ASJC) codes

Software

Keywords

Pebble game
Register allocation
Space bounds
Turing machines

Access to Document

10.1145/800113.803643

Cite this

@article{b11ed80928654b449086daa821911212,

title = "Space bounds for a game on graphs",

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.",

keywords = "Pebble game, Register allocation, Space bounds, Turing machines",

author = "Paul, {Wolfgang J.} and Tarjan, {Robert Endre} and Celoni, {James R.}",

note = "Funding Information: *~ Research partially supported by DAAD (German Academic Exchange Service) Grant No. 530/402/563/5. -~/ Research partially supported by National Science Foundation grant ~CS 72-03752 A03. ×××/ Research ~ partially supported by National Science Foundation grant DCR 72-03663 A03.; 8th Annual ACM Symposium on Theory of Computing, STOC 1976 ; Conference date: 03-05-1976 Through 05-05-1976",

year = "1976",

month = may,

day = "3",

doi = "10.1145/800113.803643",

language = "English (US)",

volume = "Part F130841",

pages = "149--160",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - Space bounds for a game on graphs

AU - Paul, Wolfgang J.

AU - Tarjan, Robert Endre

AU - Celoni, James R.

N1 - Funding Information: *~ Research partially supported by DAAD (German Academic Exchange Service) Grant No. 530/402/563/5. -~/ Research partially supported by National Science Foundation grant ~CS 72-03752 A03. ×××/ Research ~ partially supported by National Science Foundation grant DCR 72-03663 A03.

PY - 1976/5/3

Y1 - 1976/5/3

N2 - 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.

AB - 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.

KW - Pebble game

KW - Register allocation

KW - Space bounds

KW - Turing machines

UR - http://www.scopus.com/inward/record.url?scp=84943730406&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84943730406&partnerID=8YFLogxK

U2 - 10.1145/800113.803643

DO - 10.1145/800113.803643

M3 - Conference article

AN - SCOPUS:84943730406

SN - 0737-8017

VL - Part F130841

SP - 149

EP - 160

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 8th Annual ACM Symposium on Theory of Computing, STOC 1976

Y2 - 3 May 1976 through 5 May 1976

ER -

Space bounds for a game on graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this