Bashlaeva I.A., Shtelmakh T.V. Some issues of complexity of cyclic games solution on graphs

 
 
Bashlaеva Irina Alеksandrovna
 
Postgraduate Student, Department of Fundamental Informatics and Optimal Control
Volgograd State University
This email address is being protected from spambots. You need JavaScript enabled to view it. , This email address is being protected from spambots. You need JavaScript enabled to view it.
Prosp. Universitetsky, 100, 400062 Volgograd, Russian Federation
 
Shtеlmakh Tatyana Vladimirovna
 
Assistant, Department of Computer Sciences and Experimental Mathematics
Volgograd State University
This email address is being protected from spambots. You need JavaScript enabled to view it.
Prosp. Universitetsky, 100, 400062 Volgograd, Russian Federation
 
Abstract. 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. 
 
Key words: full data cyclic games, positional games, stationary Nash equilibrium, guaranteed time complexity, algorithm of potential transformations.
 
Creative Commons License

Some Issues of Complexity of Cyclic Games Solution on Graphs by Bashlaeva I.A., Shtelmakh T.V. is licensed under a Creative Commons Attribution 4.0 International License.

Citation in English: Science Journal of Volgograd State University. Mathematics. Physics. №2 (21) 2014 pp. 31-41
Attachments:
Download this file (1. Bashlaeva, Shtelmakh.pdf) 1. Bashlaeva, Shtelmakh.pdf
URL: https://mp.jvolsu.com/index.php/en/component/attachments/download/251
635 Downloads