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/