Some issues of complexity of cyclic games solution on graphs

Автор: Bashlaеva Irina Alеksandrovna, Shtеlmakh Tatyana Vladimirovna

Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu

Рубрика: Прикладная математика

Статья в выпуске: 2 (21), 2014 года.

Бесплатный доступ

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.

Full data cyclic games, positional games, stationary nash equilibrium, guaranteed time complexity, algorithm of potential transformations

Короткий адрес: https://sciup.org/14968958

IDR: 14968958

Статья научная