{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T01:13:22Z","timestamp":1785287602296,"version":"3.55.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"11","license":[{"start":{"date-parts":[[2020,10,22]],"date-time":"2020-10-22T00:00:00Z","timestamp":1603324800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GR 1492\/14-1"],"award-info":[{"award-number":["GR 1492\/14-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["820148"],"award-info":[{"award-number":["820148"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2020,10,22]]},"abstract":"<jats:p>Exploring the theoretical and practical aspects of the graph isomorphism problem.<\/jats:p>","DOI":"10.1145\/3372123","type":"journal-article","created":{"date-parts":[[2020,10,22]],"date-time":"2020-10-22T18:17:26Z","timestamp":1603390646000},"page":"128-134","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":79,"title":["The graph isomorphism problem"],"prefix":"10.1145","volume":"63","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[{"name":"TU Kaiserslautern, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,10,22]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"42","article-title":"Sherali--Adams relaxations and indistinguishability in counting logics","volume":"1","author":"Atserias A.","year":"2013","unstructured":"Atserias, A., Maneva, E. Sherali--Adams relaxations and indistinguishability in counting logics. SIAM J. Comput. 1, 42 (2013), 112--137.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_2_1","volume-title":"Universit\u00e9 de Montr\u00e9al","author":"Babai L.","year":"1979","unstructured":"Babai, L. Technical Report D.M.S. No. 79-10. Monte Carlo Algorithms in Graph Isomorphism Testing. Universit\u00e9 de Montr\u00e9al, 1979."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC'16","author":"Babai L.","year":"2016","unstructured":"Babai, L. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC'16, 2016), 684--697."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316356"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(82"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.25"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.107"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209047"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.10"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808746"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/13.1.1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90016-0"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.16"},{"key":"e_1_2_1_15_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M.R.","year":"1979","unstructured":"Garey, M.R., Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.47"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781139028868"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00018"},{"key":"e_1_2_1_19_1","first-page":"44","article-title":"Structure theorem and isomorphism test for graphs with excluded topological subgraphs","volume":"1","author":"Grohe M.","year":"2015","unstructured":"Grohe, M., Marx, D. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM J. Comput. 1, 44 (2015), 114--159.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_20_1","volume-title":"Graph isomorphisms in quasi-polynomial time. ArXiv 1710.04574","author":"Helfgott H.A.","year":"2017","unstructured":"Helfgott, H.A., Bajpai, J., Dona, D. Graph isomorphisms in quasi-polynomial time. ArXiv 1710.04574 (2017)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_13"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3329995.3330042"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.28"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of a DIMACS Workshop","author":"Luks E.M.","year":"1991","unstructured":"Luks, E.M. Permutation groups and polynomial-time computation. In Groups And Computation, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, October 7-10, 1991 (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 11), L. Finkelstein and W.M. Kantor, eds. DIMACS\/AMS, 1991, 139--176."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-8693(02)00646-4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90004-8"},{"key":"e_1_2_1_30_1","volume-title":"Congr. Numer. 30","author":"McKay B.","year":"1981","unstructured":"McKay, B. 1981. Practical graph isomorphism. Congr. Numer. 30 (1981), 45--87."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1021\/c160017a018"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188900"},{"key":"e_1_2_1_34_1","first-page":"147","article-title":"The isomorphism problem for classes of graphs that are invariant with respect to contraction. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 174","volume":"3","author":"Ponomarenko I.N","year":"1988","unstructured":"Ponomarenko, I.N. The isomorphism problem for classes of graphs that are invariant with respect to contraction. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 174, Teor. Slozhn. Vychisl. 3 (1988), 147--177, 182. (in Russian).","journal-title":"Teor. Slozhn. Vychisl."},{"key":"e_1_2_1_35_1","first-page":"126","article-title":"Finding chemical records by digital computers","author":"Ray L.C.","year":"1957","unstructured":"Ray, L.C., Kirsch, R.A. Finding chemical records by digital computers. Science 126 (1957).","journal-title":"Science"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316338"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546549"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970241096X"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/363872.363899"},{"key":"e_1_2_1_40_1","series-title":"Series 2","volume-title":"The reduction of a graph to canonical form and the algebgra which appears therein. NTI","author":"Weisfeiler B.","year":"1968","unstructured":"Weisfeiler, B., Leman, A. The reduction of a graph to canonical form and the algebgra which appears therein. NTI, Series 2 (1968). English translation by G. Ryabov. Available at: https:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3372123","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3372123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:45:06Z","timestamp":1750203906000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3372123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,22]]},"references-count":40,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2020,10,22]]}},"alternative-id":["10.1145\/3372123"],"URL":"https:\/\/doi.org\/10.1145\/3372123","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,22]]},"assertion":[{"value":"2020-10-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}