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

}