Abstract
For a number of two-player games where players alternately choose the next vertex of a simple or an elementary path in a graph, we consider the problem to determine whether, for a given game instance, there is a winning strategy for the first player. We show several of these problems to be PSPACE-complete. In some special cases, we obtain polynomial-time algorithms, based on graph rewriting or an intricate form of dynamic programming, e.g. we show GENERALIZED GEOGRAPHY and some other PSPACE-complete problems to be linear-time-solvable on graphs with constant bounded treewidth.
Original language | English |
---|---|
Pages (from-to) | 215-245 |
Number of pages | 31 |
Journal | Theoretical Computer Science |
Volume | 110 |
Issue number | 1 |
Publication status | Published - 15 Mar 1993 |