Параллельный алгоритм решения задачи об изоморфизме графов
Аннотация
Об авторе
Владимир Васильевич ВасильчиковРоссия
канд. техн. наук, зав. кафедрой вычислительных и программных систем
Список литературы
1. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co, San Francisco, 1979.
2. D. C. Schmidt and L. E. Druffel, “A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices”, Journal of the ACM (JACM), vol. 23, no. 3, pp. 433–445, 1976.
3. L. Babai, “Graph isomorphism in quasipolynomial time”, in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 684–697.
4. F. Harary, Graph theory. Addison-Wesley, 1969.
5. Y. German, O. German, and A. Dunaev, “An algorithm for establishing graph’s isomorfism”, Proceedings of BSTU. Issue 3, Physics and mathematics. Informatics, no. 2 (200), pp. 114–117, 2017.
6. V. K. Pogrebnoy and A. Pogrebnoy, “Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor”, Bulletin of the Tomsk Polytechnic University, vol. 323, no. 5, pp. 152–159, 2013.
7. V. K. Pogrebnoy and A. Pogrebnoy, “Polynomiality of method for computing graph structure integral descriptor”, Bulletin of the Tomsk Polytechnic University, vol. 323, no. 5, pp. 146–151, 2013.
8. A. Pogrebnoy, “Complete graph invariant and algorithm of its computation”, Bulletin of the Tomsk Polytechnic University, vol. 325, no. 5, pp. 110–122, 2014.
9. A. Pogrebnoy and V. K. Pogrebnoy, “Method of graph vertices differentiation and solution of the isomorphism problem”, Bulletin of the Tomsk Polytechnic University, vol. 326, no. 6, pp. 34–45, 2015.
10. A. Pogrebnoy and V. K. Pogrebnoy, “Method of graph vertices differentiation and solution of the isomorphism problem in geoinformatics”, Bulletin of the Tomsk Polytechnic University, vol. 326, no. 11, pp. 56–66, 2015.
11. B. F. Melnikov and N. P. Churikova, “Algorithms of Comparative Analysis of Two Invariants of a Graph”, Sovremennye informacionnye tehnologii i IT-obrazovanie (Modern Information Technologies and IT-Education), vol. 15, no. 1, pp. 45–51, 2019.
12. G. S. Ivanova and V. A. Ovchinnikov, “Completely described undirected graph structure”, Science and Education of the Bauman MSTU, no. 4, pp. 106–123, 2016.
13. V. V. Vasilchikov, Sredstva parallelnogo programmirovaniya dlya vychislitelnykh sistem s dinamicheskoy balansirovkoy zagruzki. YarGU, Yaroslavl, 2001.
14. V. V. Vasilchikov, “Kommunikatsionnyy modul dlya organizatsii polnosvyaznogo soedineniya kompyuterov v lokalnoy seti s ispolzovaniem .NET Framework”, Svidetelstvo o gosudarstvennoy registratsii programmy dlya EVM № 2013619925, 2013.
15. V. V. Vasilchikov, “Biblioteka podderzhki rekursivno-parallelnogo programmirovaniya dlya .NET Framework”, Svidetelstvo o gosudarstvennoy registratsii programmy dlya EVM № 2013619926, 2013.
16. V. V. Vasilchikov, “On the recursive-parallel programming for the. NET framework”, Automatic Control and Computer Sciences, vol. 48, no. 7, pp. 575–580, 2014.
17. V. V. Vasilchikov, “On optimization and parallelization of the little algorithm for solving the travelling salesman problem”, Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 551–557, 2017.
18. V. V. Vasilchikov, “On a recursive-parallel algorithm for solving the knapsack problem”, Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 810–816, 2018.
19. A. Steger and N. Wormald, “Generating random regular graphs quickly”, Combinatorics, Probability and Computing, vol. 8, no. 4, pp. 377–396, 1999.
Для цитирования:
Васильчиков В.В. Параллельный алгоритм решения задачи об изоморфизме графов. Моделирование и анализ информационных систем. 2020;27(1):86-94. https://doi.org/10.18255/1818-1015-2020-1-86-94
For citation:
Vasilchikov V.V. Parallel Algorithm for Solving the Graph Isomorphism Problem. Modeling and Analysis of Information Systems. 2020;27(1):86-94. (In Russ.) https://doi.org/10.18255/1818-1015-2020-1-86-94