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

DOI10.1007/978-3-031-09574-0_17MaRDI QIDQ2097231zbMATH OpenOpenAlexFDO

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

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