Geodesic
Some issues of complexity of cyclic games solution on graphs
Matematičeskaâ fizika i kompʹûternoe modelirovanie, no. 2 (2014), pp. 31-41.

Voir la notice de l'article provenant de la source Math-Net.Ru

The article specifies the top estimate of complexity of potential transformations algorithm for solving cyclic games on graphs. This estimate is close to the lower estimate. The authors obtained the data on optimal deviation to solving cyclic games with temporary function on the oriented graphs. The finiteness of the algorithm results in high level of complexity. The article contains the analysis of exponential estimate of algorithm's iterations.
Keywords: full data cyclic games, positional games, stationary Nash equilibrium, guaranteed time complexity, algorithm of potential transformations. 
@article{VVGUM_2014_2_a4,
     author = {I. A. Bashlaeva and T. V. Sht{\cyre}lmakh},
     title = {Some issues of complexity of cyclic games solution on graphs},
     journal = {Matemati\v{c}eska\^a fizika i kompʹ\^uternoe modelirovanie},
     pages = {31--41},
     publisher = {mathdoc},
     number = {2},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VVGUM_2014_2_a4/}
}
TY  - JOUR
AU  - I. A. Bashlaeva
AU  - T. V. Shtеlmakh
TI  - Some issues of complexity of cyclic games solution on graphs
JO  - Matematičeskaâ fizika i kompʹûternoe modelirovanie
PY  - 2014
SP  - 31
EP  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VVGUM_2014_2_a4/
LA  - ru
ID  - VVGUM_2014_2_a4
ER  - 
%0 Journal Article
%A I. A. Bashlaeva
%A T. V. Shtеlmakh
%T Some issues of complexity of cyclic games solution on graphs
%J Matematičeskaâ fizika i kompʹûternoe modelirovanie
%D 2014
%P 31-41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VVGUM_2014_2_a4/
%G ru
%F VVGUM_2014_2_a4
I. A. Bashlaeva; T. V. Shtеlmakh. Some issues of complexity of cyclic games solution on graphs. Matematičeskaâ fizika i kompʹûternoe modelirovanie, no. 2 (2014), pp. 31-41. http://geodesic.mathdoc.fr/item/VVGUM_2014_2_a4/

[1] V.\;A. Gurvich, A.\;V. Karzanov, L.\;G. Khachiyan, “Cyclic games and find the minimax of secondary cycles in oriented graphs”, Journal of Computational Mathematics and Mathematical Physics, 28:9 (1988), 1407–1417

[2] A.\;V. Karzanov, “About average weight minimum sections and cycles of oriented graph”, Qualitative research methods and approximate operator equations, 1985, 72–83

[3] E.\;M. Klark, O. Gramberg jr., D. Peled, Program models verification, Izd-vo Mosk. tsentra nepreryv. mat. obrazovaniya Publ., M., 2002, 416 pp.

[4] P. Bouyer, U. Fahrenberg, K.\;G. Larsen, N. Markey, J. Srba, “Infinite runs in weighted timed automata with energy constraints”, Formal Modeling and Analysis of Timed Systems, FORMATS 2008 (Saint Malo, France, September 15–17, 2008), LNCS, 5215, 2008, 33–47

[5] Y.\;M. Lifshits, D.\;S. Pavlov, “Potential theory for mean payoff games”, Notes of scientific seminars LBMI, 340, 2006, 61–75