Pebbling dynamic graphs in minimal space.(English)Zbl 0884.68096

Summary: Pebble game on dynamic graphs is studied as an abstract model of the incremental computations. Extreme explosion of the time complexity is related to small changes in the size of computational graphs. A class of dags $$\{G_n\}$$ of the size $$n$$ pebbleable in space $$O(n^{1/3})$$ is exhibited such that the standard pebble game requires superpolynomial time in $$n$$ under the restriction that the minimal space is used. Moreover, by deleting just one edge in $$\{G_n\}$$ a new class of graphs is obtained for which standard pebble game needs only polynomial time in $$n$$ also in the case when the minimal space is used.

MSC:

 68R10 Graph theory (including graph drawing) in computer science

Keywords:

pebble game on dynamic graphs
Full Text:

References:

 [1] 1. S. A. COOK, An Observation on Time-Storage Trade Off, Journal of Computers and System Sciences, 1974, 9, 308-316. Zbl0306.68026 MR398160 · Zbl 0306.68026 [2] 2. N. PIPPENGER, Pebbling, 5th IBM Symposium on Mathematical Foundations of Computer Science, Tokyo, 1980. [3] 3. H. VENKATESWARAN and M. TOMPA, A New Pebble Game that Characterizes Parallel Complexity Classes, S.I.A.M. J. Computing, 1989, 18, 533-549. Zbl0678.68047 MR996834 · Zbl 0678.68047 [4] 4. R. WILBER, White Pebbles Help, Journal of Computers and System Sciences, 1988, 36, 108-124. Zbl0657.68049 MR950428 · Zbl 0657.68049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.