×

Remarks on pebble games on graphs. (English) Zbl 0721.90095

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.

MSC:

91A43 Games involving graphs
68W15 Distributed algorithms
90C60 Abstract computational complexity for mathematical programming problems

Keywords:

survey; pebble games
PDFBibTeX XMLCite