TY - GEN
T1 - Time-space trade-offs in a pebble game
AU - Paul, W. J.
AU - Tarjan, R. E.
N1 - 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 -