Efficient Algorithms for Games Played on Trees with Back-edges

摘要

This paper studies algorithms for deciding the winners of two-player games played on directed graphs. We focus on the case when the underlying graphs are trees with back-edges and provide both theoretical and experimental analysis of this class of games. In particular, we present an algorithm that solves Biichi games played on trees with back-edges in time O(min{r·m,? + m}) where m is the number of edges, ￡ is the sum of the distances from the root to all leaves and the parameter r is bounded by the height of the tree. We also show that parity games played on trees with back-edges can be solved in time O(? + m).