Email this article Estimation of the Complexity of the Potential Transformation Algorithm for Solving Cyclic Games on Graphs
- Authors: Bashlaeva I.A.1, Kovkov D.V.2
-
Affiliations:
- Volgograd State University
- Federal Research Center Computer Science and Control, Russian Academy of Sciences
- Issue: Vol 58, No 3 (2019)
- Pages: 425-433
- Section: Systems Analysis and Operations Research
- URL: https://journals.rcsi.science/1064-2307/article/view/220385
- DOI: https://doi.org/10.1134/S106423071903002X
- ID: 220385
Cite item
Open Access
Access granted
Subscription Access
Abstract
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.
About the authors
I. A. Bashlaeva
Volgograd State University
Author for correspondence.
Email: bashlaeva_ia@volsu.ru
Russian Federation, Volgograd, 400062
D. V. Kovkov
Federal Research Center Computer Science and Control, Russian Academy of Sciences
Email: bashlaeva_ia@volsu.ru
Russian Federation, Moscow, 119333
