Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games

DOI10.1007/s00236-016-0276-zzbMath1362.68203OpenAlexW2364159064MaRDI QIDQ520343

Thomas Brihaye, Gilles Geeraerts, Benjamin Monmege, Axel Haddad

Publication date: 3 April 2017

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-016-0276-z

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Games involving graphs (91A43) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (7)

Optimal controller synthesis for timed systems ⋮ Computing branching distances with quantitative games ⋮ Optimal Reachability in Divergent Weighted Timed Games ⋮ Unnamed Item ⋮ On relevant equilibria in reachability games ⋮ Reaching Your Goal Optimally by Playing at Random with No Memory ⋮ Symbolic Approximation of Weighted Timed Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Faster algorithms for mean-payoff games
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• On short paths interdiction problems: Total and node-wise limited interdiction
• The bad match; a total reward stochastic game
• Positional strategies for mean payoff games
• Borel determinacy
• The complexity of mean payoff games on graphs
• Automatic verification of competitive stochastic systems
• Nash Equilibria in Concurrent Priced Games
• Adding Negative Prices to Priced Timed Games
• Multiplayer Cost Games with Simple Nash Equilibria
• Games through Nested Fixpoints
• On the synthesis of strategies in infinite games
• Mathematical Foundations of Computer Science 2004
• Negative Dynamic Programming
• Depth-First Search and Linear Graph Algorithms
• Quantitative Languages Defined by Functional Automata

This page was built for publication: Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games