Identification Conditions for the Solvability of NP-complete Problems for the Class of Pre-fractal Graphs
https://doi.org/10.18255/1818-1015-2021-2-126-135
Abstract
About the Authors
Aleksandr Vasil'evich TymoshenkoRussian Federation
Rasul Ahmatovich Kochkarov
Russian Federation
Azret Ahmatovich Kochkarov
Russian Federation
References
1. A. A. Kochkarov, R. A. Kochkarov, and G. G. Malinetskii, “Issues of dynamic graph theory,” Computational Mathematics and Mathematical Physics, vol. 55, no. 9, pp. 1590-1596, 2015.
2. S. N. Pupyrev and A. V. Tikhonov, “The Analysis of Complex Networks with Dynamic Graph Visualization,” Modeling and Analysis of Information Systems, vol. 17, no. 1, pp. 117-135, 2010.
3. Y. A. Belov and S. I. Vovchok, “Generation of a Social Network Graph by Using Apache Spark,” Modeling and Analysis of Information Systems, vol. 23, no. 6, pp. 777-783, 2016.
4. S. V. Morzhov and V. A. Sokolov, “An Effective Algorithm for Collision Resolution in Security Policy Rules,” Modeling and Analysis of Information Systems, vol. 26, no. 1, pp. 75-89, 2019.
5. A. M. Kochkarov, V. A. Perepelitsa, and I. V. Sergienko, Recognition of fractal graphs. Algorithmic approach. RAS SAO, 1998.
6. R. A. Kochkarov, “Problems of multicriteria optimization on multi-weighted prefractal graphs,” no. 17, pp. 319-328, 2014.
7. F. Harary, Graph theory. Addison-Wesley Pub. Co., 1969.
8. M. A. Iordanskii, “Constructive Classification of Graphs,” Modeling and Analysis of Information Systems, vol. 19, no. 4, pp. 144-153, 2012.
9. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
Review
For citations:
Tymoshenko A.V., Kochkarov R.A., Kochkarov A.A. Identification Conditions for the Solvability of NP-complete Problems for the Class of Pre-fractal Graphs. Modeling and Analysis of Information Systems. 2021;28(2):126-135. (In Russ.) https://doi.org/10.18255/1818-1015-2021-2-126-135