The GKK algorithm is the fastest over simple mean-payoff games

DOI10.1007/978-3-031-09574-0_17OpenAlexW3206569936MaRDI QIDQ2097231FDOQ2097231

Authors: Pierre Ohlmann 

Publication date: 11 November 2022

Full work available at URL: https://arxiv.org/abs/2110.04533

zbMATH Keywords

mean-payoff gamespseudopolynomialsymmetric algorithmGKK algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• The complexity of mean payoff games on graphs
• Borel determinacy
• Maximum-Minimum Sätze über Graphen
• Positional strategies for mean payoff games
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Mean cost cyclical games
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Faster algorithms for mean-payoff games
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Combinatorial structure and randomized subexponential algorithms for infinite games
• Deciding parity games in quasipolynomial time
• Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
• A faster deterministic exponential time algorithm for energy games and mean payoff games

This page was built for publication: The GKK algorithm is the fastest over simple mean-payoff games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097231)