TY - GEN

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

AU - Paul, W. J.

AU - Tarjan, R. E.

N1 - Funding Information:
2) Research partially supported by the National Science Foundation~ Grant No. MCS 75-22870 and by the Office of Naval Research~ Contract No. N ooi&-76-C-o688.
Funding Information:
The game models time and space requirements of computations in the following sense. The nodes of G correspond to operations and the pebbles correspond to storage locations. If a pebble is on a node this means that the result o£ the operation to which the node corresponds is stored in some storage location. Thus the rules have the following meaning: !) Research partially supperted by DAAD (German Academic Exchange Service) Grant No. ~3o/~o2/653/5.
Publisher Copyright:
© 1977, Springer-Verlag.

PY - 1977

Y1 - 1977

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 -