An average polynomial algorithm for solving antagonistic games on graphs

DOI10.1134/S1064230718010045zbMath1394.05078OpenAlexW2792036561MaRDI QIDQ1647454

Vladimir I. Tsurkov, Vasilij N. Lebedev

Publication date: 26 June 2018

Published in: Journal of Computer and Systems Sciences International (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1064230718010045

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (1)

Estimation of the complexity of the potential transformation algorithm for solving cyclic games on graphs

Cites Work

• Unnamed Item
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Cyclic games and linear programming
• Positional strategies for mean payoff games
• A characterization of the minimum cycle mean in a digraph
• The complexity of mean payoff games on graphs
• Optimization of schedules with precedence logical conditions
• Mean Cost Cyclical Games
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Typical Properties of Winners and Losers [0.2ex in Discrete Optimization]
• Contraction Mappings in the Theory Underlying Dynamic Programming

This page was built for publication: An average polynomial algorithm for solving antagonistic games on graphs