Rytter, W. Remarks on pebble games on graphs. (English) Zbl 0721.90095 Zastosow. Mat. 19, No. 3-4, 569-577 (1987). Summary: We briefly survey some applications of pebble games to main problems in complexity theory. In the second part of the paper we analyze a new pebble game introduced by the author and relate it to the complexity of parallel computations. This new game changes the structure of the graph during the game, adding some extra edges, while previously known games are played on static graphs. Cited in 3 Documents MSC: 91A43 Games involving graphs 68W15 Distributed algorithms 90C60 Abstract computational complexity for mathematical programming problems Keywords:survey; pebble games PDFBibTeX XMLCite \textit{W. Rytter}, Zastosow. Mat. 19, No. 3--4, 569--577 (1987; Zbl 0721.90095)