Time-space trade-offs in a pebble game

W. J. Paul; R. E. Tarjan

doi:10.1007/BF00289150

Time-space trade-offs in a pebble game

W. J. Paul, R. E. Tarjan

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

21 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 G_n and constants c₁, c₂, c₃ such that (1) G_n has n nodes and each node in G_n has indegree at most 2. (2) Each graph G_n can be pebbled with c₁√n pebbles in n moves. (3) Each graph G_n can also be pebbled with c₂√n pebbles, c₂<c₁, but every strategy which achieves this has at least 2^c₃√n moves.

Original language	English (US)
Pages (from-to)	111-115
Number of pages	5
Journal	Acta Informatica
Volume	10
Issue number	2
DOIs	https://doi.org/10.1007/BF00289150
State	Published - Jun 1978
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Information Systems
Computer Networks and Communications

Access to Document

10.1007/BF00289150

Cite this

@article{82a2f47a38ae46a6a2009d3569dd9cf0,

title = "Time-space trade-offs in a pebble game",

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, c21, but every strategy which achieves this has at least 2c3√n moves.",

author = "Paul, {W. J.} and Tarjan, {R. E.}",

year = "1978",

month = jun,

doi = "10.1007/BF00289150",

language = "English (US)",

volume = "10",

pages = "111--115",

journal = "Acta Informatica",

issn = "0001-5903",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Time-space trade-offs in a pebble game

AU - Paul, W. J.

AU - Tarjan, R. E.

PY - 1978/6

Y1 - 1978/6

N2 - 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, c21, but every strategy which achieves this has at least 2c3√n moves.

AB - 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, c21, but every strategy which achieves this has at least 2c3√n moves.

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

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

U2 - 10.1007/BF00289150

DO - 10.1007/BF00289150

M3 - Article

AN - SCOPUS:0347505392

SN - 0001-5903

VL - 10

SP - 111

EP - 115

JO - Acta Informatica

JF - Acta Informatica

IS - 2

ER -

Time-space trade-offs in a pebble game

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this