An Average Polynomial Algorithm for Solving Antagonistic Games on Graphs
- 作者: Lebedev V.1, Tsurkov V.2
-
隶属关系:
- Volgograd State University
- Trapeznikov Institute of Control Sciences
- 期: 卷 57, 编号 1 (2018)
- 页面: 88-96
- 栏目: Discrete Systems
- URL: https://journals.rcsi.science/1064-2307/article/view/220061
- DOI: https://doi.org/10.1134/S1064230718010045
- ID: 220061
如何引用文章
详细
An algorithm that determines the winner in a cyclic game in polynomial time is proposed. The two-person game occurs continuously on the edges of a directed graph until a vertex visited earlier is reached. If the weight of the resulting cycle is nonnegative, then the maximizing player wins; if this cycle has a negative weight, then the minimizing player wins. A polynomial estimate of the expected algorithm execution time is obtained under the condition that the weights of the game’s graph edges are distributed uniformly. A brief justification of the time estimate of the algorithm is given. Such games have applications in the validating the correctness of parallel-distributed computer systems, including problems of making up a feasible schedule with logical precedence conditions and preprocessing possibilities.
作者简介
V. Lebedev
Volgograd State University
Email: tsur@ccas.ru
俄罗斯联邦, Volgograd
V. Tsurkov
Trapeznikov Institute of Control Sciences
编辑信件的主要联系方式.
Email: tsur@ccas.ru
俄罗斯联邦, Moscow, 117997
![](/img/style/loading.gif)