A certain pebble game on graphs has been studied in various contexts as a model for the time and space requirements of computations [1,2,3,8]. In this note it is shown that there exists a family of directed acyclic graphs Gn and constants c1, c2, c3 such that (1) 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 2c 3√n moves.
All Science Journal Classification (ASJC) codes
- Information Systems
- Computer Networks and Communications