An Average Polynomial Algorithm for Solving Antagonistic Games on Graphs

作者：Lebedev V N; Tsurkov V I^*

来源：Journal of Computer and Systems Sciences International, 2018, 57(1): 88-96.

DOI：10.1134/S1064230718010045

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.

• 出版日期2018-1