Complexity of path-forming games

Hans L. Bodlaender*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

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 languageEnglish
Pages (from-to)215-245
Number of pages31
JournalTheoretical Computer Science
Volume110
Issue number1
Publication statusPublished - 15 Mar 1993

Fingerprint

Dive into the research topics of 'Complexity of path-forming games'. Together they form a unique fingerprint.

Cite this