Estimation of the Complexity of the Potential Transformation Algorithm for Solving Cyclic Games on Graphs
- Autores: Bashlaeva I.1, Kovkov D.2
-
Afiliações:
- Volgograd State University
- Federal Research Center Computer Science and Control, Russian Academy of Sciences
- Edição: Volume 58, Nº 3 (2019)
- Páginas: 425-433
- Seção: Systems Analysis and Operations Research
- URL: https://journals.rcsi.science/1064-2307/article/view/220385
- DOI: https://doi.org/10.1134/S106423071903002X
- ID: 220385
Citar
Resumo
The upper bound on the complexity of the potential transformation algorithm for solving cyclic games on graphs is improved. This bound is close to the lower bound on the complexity of the potential transformation algorithm. The optimal deviation problem is reduced to a cyclic game on a directed graph.
Sobre autores
I. Bashlaeva
Volgograd State University
Autor responsável pela correspondência
Email: bashlaeva_ia@volsu.ru
Rússia, Volgograd, 400062
D. Kovkov
Federal Research Center Computer Science and Control, Russian Academy of Sciences
Email: bashlaeva_ia@volsu.ru
Rússia, Moscow, 119333