@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",
}