{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:10:59Z","timestamp":1773655859234,"version":"3.50.1"},"reference-count":19,"publisher":"Allerton Press","issue":"7","license":[{"start":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:00:00Z","timestamp":1638316800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:00:00Z","timestamp":1638316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Aut. Control Comp. Sci."],"published-print":{"date-parts":[[2021,12]]},"DOI":"10.3103\/s0146411621070166","type":"journal-article","created":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T09:15:43Z","timestamp":1643706943000},"page":"617-622","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Parallel Algorithm for Solving the Graph Isomorphism Problem"],"prefix":"10.3103","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7882-8906","authenticated-orcid":false,"given":"V. V.","family":"Vasilchikov","sequence":"first","affiliation":[]}],"member":"1627","published-online":{"date-parts":[[2022,2,1]]},"reference":[{"key":"7391_CR1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco: W.H. Freeman Co., 1979."},{"key":"7391_CR2","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1145\/321958.321963","volume":"23","author":"D.C. Schmidt","year":"1976","unstructured":"Schmidt, D.C. and Druffel, L.E., A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices, J. ACM, 1976, vol. 23, no. 3, pp. 433\u2013445.","journal-title":"J. ACM"},{"key":"7391_CR3","doi-asserted-by":"crossref","unstructured":"Babai, L., Graph isomorphism in quasipolynomial time, Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, 2016, pp. 684\u2013697.","DOI":"10.1145\/2897518.2897542"},{"key":"7391_CR4","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"Harary, F., Graph Theory, Addison-Wesley, 1969."},{"key":"7391_CR5","unstructured":"German, Y., German, O., and Dunaev, A., An algorithm for establishing graph\u2019s isomorfism, Proc. BSTI, Issue 3, Phys. Math. Inf., 2017, no. 2, pp. 114\u2013117."},{"key":"7391_CR6","first-page":"152","volume":"323","author":"V.K. Pogrebnoy","year":"2013","unstructured":"Pogrebnoy, V.K. and Pogrebnoy, A., Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor, Bull. Tomsk Polytech. Univ., 2013, vol. 323, no. 5, pp. 152\u2013159.","journal-title":"Bull. Tomsk Polytech. Univ."},{"key":"7391_CR7","first-page":"146","volume":"323","author":"V.K. Pogrebnoy","year":"2013","unstructured":"Pogrebnoy, V.K. and Pogrebnoy, A., Polynomiality of method for computing graph structure integral descriptor, Bull. Tomsk Polytech. Univ., 2013, vol. 323, no. 5, pp. 146\u2013151.","journal-title":"Bull. Tomsk Polytech. Univ."},{"key":"7391_CR8","first-page":"110","volume":"325","author":"A. Pogrebnoy","year":"2014","unstructured":"Pogrebnoy, A., Complete graph invariant and algorithm of its computation, Bull. Tomsk Polytech. Univ., 2014, vol. 325, no. 5, pp. 110\u2013122.","journal-title":"Bull. Tomsk Polytech. Univ."},{"key":"7391_CR9","first-page":"34","volume":"326","author":"A. Pogrebnoy","year":"2015","unstructured":"Pogrebnoy, A. and Pogrebnoy, V.K., Method of graph vertices differentiation and solution of the isomorphism problem, Bull. Tomsk Polytech. Univ., 2015, vol. 326, no. 6, pp. 34\u201345.","journal-title":"Bull. Tomsk Polytech. Univ."},{"key":"7391_CR10","first-page":"56","volume":"326","author":"A. Pogrebnoy","year":"2015","unstructured":"Pogrebnoy, A. and Pogrebnoy, V.K., Method of graph vertices differentiation and solution of the isomorphism problem in geoinformatics, Bull. Tomsk Polytech. Univ., 2015, vol. 326, no. 11, pp. 56\u201366.","journal-title":"Bull. Tomsk Polytech. Univ."},{"key":"7391_CR11","first-page":"45","volume":"15","author":"B.F. Melnikov","year":"2019","unstructured":"Melnikov, B.F. and Churikova, N.P., Algorithms of comparative analysis of two invariants of a graph, Sovrem. Inf. Tekhnol. \n               IT-Obraz., 2019, vol. 15, no. 1, pp. 45\u201351.","journal-title":"IT-Obraz."},{"key":"7391_CR12","doi-asserted-by":"crossref","unstructured":"Ivanova, G.S. and Ovchinnikov, V.A., Completely described undirected graph structure, Sci. Educ. Bauman MSTU, 2016, no. 4, pp. 106\u2013123.","DOI":"10.7463\/0416.0835978"},{"key":"7391_CR13","unstructured":"Vasilchikov, V.V., Sredstva parallel\u2019nogo programmirovaniya dlya vychislitel\u2019nykh sistem s dinamicheskoi balansirovkoi zagruzki (Parallel Programming Tools for Computing Systems with Dynamic Load Balancing), Yaroslavl: YarGU, 2001."},{"key":"7391_CR14","unstructured":"Vasilchikov, V.V., Communication module for organizing a fully connected joining of computers in a local network using .NET Framework, Certificate of State Registration of Computer Program, 2013, no. 2013619925."},{"key":"7391_CR15","unstructured":"Vasilchikov, V.V., Recursive-parallel programming support library for .NET Framework, Certificate of State Registration of Computer Program, 2013, no. 2013619926."},{"key":"7391_CR16","doi-asserted-by":"publisher","first-page":"575","DOI":"10.3103\/S014641161407030X","volume":"48","author":"V.V. Vasilchikov","year":"2014","unstructured":"Vasilchikov, V.V., On the recursive-parallel programming for the. NET framework, Autom. Control Comput. Sci., 2014, vol. 48, no. 7, pp. 575\u2013580.","journal-title":"Autom. Control Comput. Sci."},{"key":"7391_CR17","doi-asserted-by":"publisher","first-page":"551","DOI":"10.3103\/S0146411617070215","volume":"51","author":"V.V. Vasilchikov","year":"2017","unstructured":"Vasilchikov, V.V., On optimization and parallelization of the little algorithm for solving the travelling salesman problem, Autom. Control Comput. Sci., 2017, vol. 51, no. 7, pp. 551\u2013557.","journal-title":"Autom. Control Comput. Sci."},{"key":"7391_CR18","doi-asserted-by":"publisher","first-page":"810","DOI":"10.3103\/S014641161807026X","volume":"52","author":"V.V. Vasilchikov","year":"2018","unstructured":"Vasilchikov, V.V., On a recursive-parallel algorithm for solving the knapsack problem, Autom. Control Comput. Sci., 2018, vol. 52, no. 7, pp. 810\u2013816.","journal-title":"Autom. Control Comput. Sci."},{"key":"7391_CR19","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1017\/S0963548399003867","volume":"8","author":"A. Steger","year":"1999","unstructured":"Steger, A. and Wormald, N., Generating random regular graphs quickly, Comb. Probab. Comput., 1999, vol. 8, no. 4, pp. 377\u2013396.","journal-title":"Comb. Probab. Comput."}],"container-title":["Automatic Control and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411621070166.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.3103\/S0146411621070166","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411621070166.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T22:07:44Z","timestamp":1773612464000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.3103\/S0146411621070166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12]]},"references-count":19,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["7391"],"URL":"https:\/\/doi.org\/10.3103\/s0146411621070166","relation":{},"ISSN":["0146-4116","1558-108X"],"issn-type":[{"value":"0146-4116","type":"print"},{"value":"1558-108X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12]]},"assertion":[{"value":"16 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The author declares that he has no conflicts of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"CONFLICT OF INTEREST"}}]}}