Back to Search
Start Over
An Average Polynomial Algorithm for Solving Antagonistic Games on Graphs
- Source :
- Journal of Computer and Systems Sciences International. 57:88-96
- Publication Year :
- 2018
- Publisher :
- Pleiades Publishing Ltd, 2018.
-
Abstract
- 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.
- Subjects :
- Vertex (graph theory)
Computer Science::Computer Science and Game Theory
0209 industrial biotechnology
Correctness
Computer Networks and Communications
Computer science
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
020901 industrial engineering & automation
Preprocessor
Time complexity
Discrete mathematics
business.industry
Applied Mathematics
Robotics
Directed graph
Mechatronics
Graph
010201 computation theory & mathematics
Control and Systems Engineering
Computer Vision and Pattern Recognition
Artificial intelligence
business
Software
Information Systems
Subjects
Details
- ISSN :
- 15556530 and 10642307
- Volume :
- 57
- Database :
- OpenAIRE
- Journal :
- Journal of Computer and Systems Sciences International
- Accession number :
- edsair.doi...........8edda527689c5c44a7a865971b5cf308