Space bounds for a game on graphs

ABSTRACT

We study a one-person game played by placing pebbles, according to certain rules, on the vertices of a directed graph. In [3] it was shown that for each graph with n vertices and maximum in-degree d , there is a pebbling strategy which requires at most c(d) n/log n pebbles. Here we show that this bound is tight to within a constant factor. We also analyze a variety of pebbling algorithms, including one which achieves the 0(n/log n) bound.

REFERENCES

• 1: Stephen A. Cook, An observation on time-storage trade off, Proceedings of the fifth annual ACM symposium on Theory of computing, p.29-33, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804032]
• 2: Paul Erdoes , Ronald L. Graham , Endre Szemeredi, On sparse graphs with dense long paths., Stanford University, Stanford, CA, 1975
• 3: J. Hopcroft, W. Paul, and L. Valiant, "On time versus space and related problems," Sixteenth Annual Symp. on Foundations of Computer Science (1975), 57-64.
• 4: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 5: M. S. Paterson and C. E. Hewitt, "Comparative schematology," Record of Project MAC Conf. on Concurrent Systems and Parallel Computation (1970), 119-128.
• 6: M. S. Paterson, "Tape bounds for time-bounded Turing machines," Journal of Comp. and Sys. Sci. 6 (1972), 116-124.
• 7: Ravi Sethi, Complete register allocation problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.182-195, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804049]
• 8: Leslie G. Valiant, On non-linear lower bounds in computational complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.45-53, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803752]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Theory

Keywords:
Pebble game, Register allocation, Space bounds, Turing machines