Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games
DOI10.1007/S00236-016-0276-ZzbMATH Open1362.68203OpenAlexW2364159064MaRDI QIDQ520343FDOQ520343
Authors: Thomas Brihaye, G. Geeraerts, Axel Haddad, Benjamin Monmege 
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
Recommendations
- To reach or not to reach? Efficient algorithms for total-payoff games
- Faster algorithms for mean-payoff games
- Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
- A pseudo-quasi-polynomial algorithm for mean-payoff parity games
- The complexity of mean payoff games on graphs
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)
Cites Work
- The complexity of mean payoff games on graphs
- Title not available (Why is that?)
- Depth-First Search and Linear Graph Algorithms
- Borel determinacy
- Positional strategies for mean payoff games
- Automatic verification of competitive stochastic systems
- On short paths interdiction problems: Total and node-wise limited interdiction
- On the synthesis of strategies in infinite games
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- Negative Dynamic Programming
- Faster algorithms for mean-payoff games
- Quantitative Languages Defined by Functional Automata
- The bad match; a total reward stochastic game
- Nash equilibria in concurrent priced games
- Adding negative prices to priced timed games
- Multiplayer cost games with simple Nash equilibria
- Games through Nested Fixpoints
- Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
- Simple priced timed games are not that simple
- Mathematical Foundations of Computer Science 2004
- To reach or not to reach? Efficient algorithms for total-payoff games
Cited In (9)
- Reaching Your Goal Optimally by Playing at Random with No Memory
- Symbolic Approximation of Weighted Timed Games
- Title not available (Why is that?)
- To reach or not to reach? Efficient algorithms for total-payoff games
- On relevant equilibria in reachability games
- Optimal reachability in divergent weighted timed games
- Computing branching distances with quantitative games
- Optimal controller synthesis for timed systems
- Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
This page was built for publication: Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q520343)
