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 -