Showing cs.GTShow all
3 papers · 1 filter
cs.GT2021
The GKK Algorithm is the Fastest over Simple Mean-Payoff Games
Pierre Ohlmann
We study the algorithm of Gurvich, Khachyian and Karzanov (GKK algorithm) when it is ran over mean-payoff games with no simple cycle of weight zero. We propose a new symmetric anal…
cs.GT2021
New Algorithms for Combinations of Objectives using Separating Automata
Ashwani Anand, Nathanaël Fijalkow, Aliénor Goubault-Larrecq +2
The notion of separating automata was introduced by Bojanczyk and Czerwinski for understanding the first quasipolynomial time algorithm for parity games. In this paper we show that…
cs.GT2018
The complexity of mean payoff games using universal graphs
Nathanaël Fijalkow, Paweł Gawrychowski, Pierre Ohlmann
We study the computational complexity of solving mean payoff games. This class of games can be seen as an extension of parity games, and they have similar complexity status: in bot…