Showing 2021Show all
2 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…