Space bounds for a game on graphs

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

doi:10.1007/BF01683275

Space bounds for a game on graphs

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

Research output: Contribution to journal › Article › peer-review

92 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 language	English (US)
Pages (from-to)	239-251
Number of pages	13
Journal	Mathematical Systems Theory
Volume	10
Issue number	1
DOIs	https://doi.org/10.1007/BF01683275
State	Published - Dec 1976
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Mathematics
Computational Theory and Mathematics

Keywords

Pebble game
Register allocation
Space bounds
Turing machines

Access to Document

10.1007/BF01683275

Cite this

@article{0a10c0414ff74e5496509ef96f3bf353,

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 0(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.\}",

year = "1976",

month = dec,

doi = "10.1007/BF01683275",

language = "English (US)",

volume = "10",

pages = "239--251",

journal = "Mathematical Systems Theory",

issn = "0025-5661",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Space bounds for a game on graphs

AU - Paul, Wolfgang J.

AU - Tarjan, Robert Endre

AU - Celoni, James R.

PY - 1976/12

Y1 - 1976/12

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

KW - Pebble game

KW - Register allocation

KW - Space bounds

KW - Turing machines

UR - https://www.scopus.com/pages/publications/0000442754

UR - https://www.scopus.com/pages/publications/0000442754#tab=citedBy

U2 - 10.1007/BF01683275

DO - 10.1007/BF01683275

M3 - Article

AN - SCOPUS:0000442754

SN - 0025-5661

VL - 10

SP - 239

EP - 251

JO - Mathematical Systems Theory

JF - Mathematical Systems Theory

IS - 1

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