Time-space trade-offs in a pebble game

W. J. Paul; R. E. Tarjan

doi:10.1007/3-540-08342-1_28

Time-space trade-offs in a pebble game

W. J. Paul, R. E. Tarjan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

Abstract

A certain pebble game on graphs has been studied in various contexts as a model for time and space requirements of computations [1,2,3,7]. In this note it is shown that there exists a family of directed acyclic graphs G_n and constants c₁,c₂,c₃ such that1)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^C3√n moves.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 4th Colloquium
Editors	Arto Salomaa, Magnus Steinby
Publisher	Springer Verlag
Pages	365-369
Number of pages	5
ISBN (Print)	9783540083429
DOIs	https://doi.org/10.1007/3-540-08342-1_28
State	Published - Jan 1 1977
Externally published	Yes
Event	4th International Colloquium on Automata, Languages and Programming, ICALP 1977 - Turku, Finland Duration: Jul 18 1977 → Jul 22 1977

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	52 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	4th International Colloquium on Automata, Languages and Programming, ICALP 1977
Country	Finland
City	Turku
Period	7/18/77 → 7/22/77

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-08342-1_28

Fingerprint Dive into the research topics of 'Time-space trade-offs in a pebble game'. Together they form a unique fingerprint.

Cite this

Paul, W. J., & Tarjan, R. E. (1977). Time-space trade-offs in a pebble game. In A. Salomaa, & M. Steinby (Eds.), Automata, Languages and Programming - 4th Colloquium (pp. 365-369). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 52 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-08342-1_28

@inproceedings{b89868c2d77b447da0a9b18326d715ef,

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 time and space requirements of computations [1,2,3,7]. In this note it is shown that there exists a family of directed acyclic graphs Gn and constants c1,c2,c3 such that1)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, c2 < c1, but every strategy which achieves this has at least 2C3√n moves.",

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

year = "1977",

month = jan,

day = "1",

doi = "10.1007/3-540-08342-1_28",

language = "English (US)",

isbn = "9783540083429",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "365--369",

editor = "Arto Salomaa and Magnus Steinby",

booktitle = "Automata, Languages and Programming - 4th Colloquium",

address = "Germany",

note = "4th International Colloquium on Automata, Languages and Programming, ICALP 1977 ; Conference date: 18-07-1977 Through 22-07-1977",

}

Paul, WJ & Tarjan, RE 1977, Time-space trade-offs in a pebble game. in A Salomaa & M Steinby (eds), Automata, Languages and Programming - 4th Colloquium. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 52 LNCS, Springer Verlag, pp. 365-369, 4th International Colloquium on Automata, Languages and Programming, ICALP 1977, Turku, Finland, 7/18/77. https://doi.org/10.1007/3-540-08342-1_28

Time-space trade-offs in a pebble game. / Paul, W. J.; Tarjan, R. E.

Automata, Languages and Programming - 4th Colloquium. ed. / Arto Salomaa; Magnus Steinby. Springer Verlag, 1977. p. 365-369 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 52 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Paul, W. J.

AU - Tarjan, R. E.

PY - 1977/1/1

Y1 - 1977/1/1

N2 - A certain pebble game on graphs has been studied in various contexts as a model for time and space requirements of computations [1,2,3,7]. In this note it is shown that there exists a family of directed acyclic graphs Gn and constants c1,c2,c3 such that1)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, c2 < c1, 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 time and space requirements of computations [1,2,3,7]. In this note it is shown that there exists a family of directed acyclic graphs Gn and constants c1,c2,c3 such that1)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, c2 < c1, but every strategy which achieves this has at least 2C3√n moves.

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

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

U2 - 10.1007/3-540-08342-1_28

DO - 10.1007/3-540-08342-1_28

M3 - Conference contribution

AN - SCOPUS:84915558395

SN - 9783540083429

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 365

EP - 369

BT - Automata, Languages and Programming - 4th Colloquium

A2 - Salomaa, Arto

A2 - Steinby, Magnus

PB - Springer Verlag

T2 - 4th International Colloquium on Automata, Languages and Programming, ICALP 1977

Y2 - 18 July 1977 through 22 July 1977

ER -