We introduce the notion of universal graphs as a tool for constructing algorithms solving games of infinite duration such as parity games and mean payoff games. In the first part we develop the theory of universal graphs, with two goals: showing an equivalence and normalisation result between different recently introduced related models, and constructing generic value iteration algorithms for any positionally determined objective. In the second part we give four applications: to parity games, to mean payoff games, and to combinations of them (in the form of disjunctions of objectives). For each of these four cases we construct algorithms achieving or improving over the best known time and space complexity.

翻译：我们引入通用图形的概念,作为构建解决无限持续游戏的算法的工具,比如平价游戏和平均收益游戏。 在第一部分,我们发展通用图形理论,有两个目标:显示最近引入的不同相关模型之间的等值和正常化结果,为任何定位确定的目标构建通用值迭代算法。在第二部分,我们给出四个应用:对等游戏,意味着报酬游戏,以及它们的组合(以目标脱钩的形式 ) 。 对于这四个案例中的每一案例,我们构建了在已知的最佳时间和空间复杂度上实现或改进的算法。