Top

Journal of Computer and Systems Sciences International

Published in:

01-05-2019 | SYSTEMS ANALYSIS AND OPERATIONS RESEARCH

Estimation of the Complexity of the Potential Transformation Algorithm for Solving Cyclic Games on Graphs

Authors: I. A. Bashlaeva, D. V. Kovkov

Published in: Journal of Computer and Systems Sciences International | Issue 3/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Mathematical Modeling of the Operation of Pension Funds in Order to Assess Their Sustainability

next article Neural Network Training System for Marker Encoding

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

V. A. Gurvich, A. V. Karzanov, and L. G. Khachiyan, “Cyclic games and finding minimax average cycles in directed graphs,” Zh. Vychisl. Mat. Mat. Fiz. 28, 1407–1417 (1988).MATH

D. V. Alifanov, V. N. Lebedev, and V. I. Tsurkov, “Optimization of schedules with precedence logical conditions,” J. Comput. Syst. Sci. Int. 48, 932 (2009).MathSciNetCrossRefMATH

V. N. Lebedev and V. I. Tsurkov, “An average polynomial algorithm for solving antagonistic games on graphs,” J. Comput. Syst. Sci. Int. 57, 88 (2018).MathSciNetCrossRefMATH

U. Zwick and M. Paterson, “The complexity of mean payoff games on graphs,” Theor. Comput. Sci. 158, 343–359 (1996).MathSciNetCrossRefMATH

D. Andersson and P. B. Miltersen, “The complexity of solving stochastic games on graphs,” Lect. Notes Comput. Sci. 5878, 112 (2009).MathSciNetCrossRefMATH

K. Daskalakis and C. H. Papadimitriou, “The complexity of games on highly regular graphs,” Lect. Notes Comput. Sci. 3669, 71 (2005).MathSciNetCrossRefMATH

A. S. Fraenkel and Y. Yesha, “Complexity of problems in games, graphs and algebraic equations,” Discrete Appl. Math. 1, 15–30 (1979).MathSciNetCrossRefMATH

D. Berwanger and E. Graedel, “Entanglement—a measure for the complexity of directed graphs with applications to logic and games,” Lect. Notes Comput. Sci. 3452, 209 (2005).MathSciNetCrossRefMATH

A. S. Goldstein and E. M. Reingold, “The complexity of pursuit on a graph,” Theor. Comput. Sci. 143, 93–112 (1995).MathSciNetCrossRefMATH

10.

T. J. Schaffer, “On the complexity of some two-person perfect-information games,” J. Comput. Syst. Sci. 16, 185–225 (1978).MathSciNetCrossRef

11.

Y. M. Lifshits and D. S. Pavlov, “Potenial theory for mean pay-off games,” Zap. Nauch. Seminarov LOMI 340, 61–75 (2006).

12.

E. M. Clarke, Jr., O. Grumberg, D. Kroening, D. Peled, and H. Veith, Model Checking (MIT Press, Boston, MA, 2018).

13.

A. A. Mironov, V. V. Fedorchuk, and V. I. Tsurkov, “Minimax in transportation models with integral constraints: I,” J. Comput. Syst. Sci. Int. 42, 562 (2003).MATH

14.

A. A. Mironov, V. V. Fedorchuk, and V. I. Tsurkov, “Minimax in transportation models with integral constraints: II,” J. Comput. Syst. Sci. Int. 44, 732 (2005).MATH

Title: Estimation of the Complexity of the Potential Transformation Algorithm for Solving Cyclic Games on Graphs
Authors: I. A. Bashlaeva
D. V. Kovkov
Publication date: 01-05-2019
Publisher: Pleiades Publishing
Published in: Journal of Computer and Systems Sciences International / Issue 3/2019
Print ISSN: 1064-2307
Electronic ISSN: 1555-6530
DOI: https://doi.org/10.1134/S106423071903002X

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2019

Fusion of Images of Different Spectra Based on Generative Adversarial Networks

Method of Parametric Optimization of Nonlinear Continuous Systems of Joint Estimation and Control

Calculation of Program Controls Not Generating Singular States of a Gyro System. II

Optimal Control of Rotation of a Rigid Body by a Movable Internal Mass

Stabilization of a Moving Object in a Neighborhood of an Instable Equilibrium: Some Peculiarities of Problem Statement

Neural Network Training System for Marker Encoding

Premium Partner