Faster O(|V|^2|E|W)-Time Energy Algorithms for Optimal Strategy Synthesis in Mean Payoff Games

Carlo Comin, Romeo Rizzi

This study strengthens the links between Mean Payoff Games (\MPG{s}) and Energy Games (EG{s}). Firstly, we offer a faster $O(|V{|}^2|E|W)$ pseudo-polynomial time and $\Theta (|V|+|E|)$ spa…