{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T10:01:10Z","timestamp":1764842470127,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030752415"},{"type":"electronic","value":"9783030752422"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-75242-2_17","type":"book-chapter","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T15:22:29Z","timestamp":1620141749000},"page":"245-257","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Weisfeiler-Leman Algorithm and\u00a0Recognition of Graph Properties"],"prefix":"10.1007","author":[{"given":"Frank","family":"Fuhlbr\u00fcck","sequence":"first","affiliation":[]},{"given":"Johannes","family":"K\u00f6bler","sequence":"additional","affiliation":[]},{"given":"Ilia","family":"Ponomarenko","sequence":"additional","affiliation":[]},{"given":"Oleg","family":"Verbitsky","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,4]]},"reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0095-8956(73)90027-0","volume":"15","author":"B Alspach","year":"1973","unstructured":"Alspach, B.: Point-symmetric graphs and digraphs of prime order and transitive permutation groups of prime degree. J. Comb. Theory Ser. B 15, 12\u201317 (1973)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3\u20134","key":"17_CR2","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF01895854","volume":"29","author":"L Babai","year":"1977","unstructured":"Babai, L.: Isomorphism problem for a class of point-symmetric structures. Acta Math. Acad. Sci. Hungar. 29(3\u20134), 329\u2013336 (1977). https:\/\/doi.org\/10.1007\/BF01895854","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"17_CR3","doi-asserted-by":"publisher","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016), pp. 684\u2013697 (2016). https:\/\/doi.org\/10.1145\/2897518.2897542","DOI":"10.1145\/2897518.2897542"},{"key":"17_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1939-6","volume-title":"Spectra of Graphs","author":"AE Brouwer","year":"2012","unstructured":"Brouwer, A.E., Haemers, W.H.: Spectra of Graphs. Springer, Berlin (2012). https:\/\/doi.org\/10.1007\/978-1-4614-1939-6"},{"issue":"4","key":"17_CR5","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J Cai","year":"1992","unstructured":"Cai, J., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identifications. Combinatorica 12(4), 389\u2013410 (1992). https:\/\/doi.org\/10.1007\/BF01305232","journal-title":"Combinatorica"},{"key":"17_CR6","unstructured":"Chen, G., Ponomarenko, I.: Coherent Configurations. Central China Normal University Press, Wuhan (2019), a draft version is available at http:\/\/www.pdmi.ras.ru\/~inp\/ccNOTES.pdf"},{"issue":"6","key":"17_CR7","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1090\/S1061-0022-04-00833-7","volume":"15","author":"S Evdokimov","year":"2004","unstructured":"Evdokimov, S., Ponomarenko, I.: Circulant graphs: recognizing and isomorphism testing in polynomial time. St. Petersbg. Math. J. 15(6), 813\u2013835 (2004)","journal-title":"St. Petersbg. Math. J."},{"key":"17_CR8","unstructured":"Evdokimov, S.: Schurity and separability of association schemes. Ph.D. thesis, St. Petersburg University, St. Petersburg (2004)"},{"key":"17_CR9","unstructured":"Evdokimov, S., Ponomarenko, I.: On highly closed cellular algebras and highly closed isomorphisms. Electr. J. Comb. 6 (1999). http:\/\/www.combinatorics.org\/Volume_6\/Abstracts\/v6i1r18.html"},{"issue":"1\u20133","key":"17_CR10","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0012-365X(00)00152-7","volume":"225","author":"S Evdokimov","year":"2000","unstructured":"Evdokimov, S., Ponomarenko, I., Tinhofer, G.: Forestal algebras and algebraic forests (on a new class of weakly compact graphs). Discrete Math. 225(1\u20133), 149\u2013172 (2000). https:\/\/doi.org\/10.1016\/S0012-365X(00)00152-7","journal-title":"Discrete Math."},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Fuhlbr\u00fcck, F., K\u00f6bler, J., Ponomarenko, I., Verbitsky, O.: The Weisfeiler-Leman algorithm and recognition of graph properties. Tech. rep. arxiv.org\/abs\/2005.08887 (2020)","DOI":"10.1007\/978-3-030-75242-2_17"},{"key":"17_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-319-57586-5_22","volume-title":"Algorithms and Complexity","author":"M F\u00fcrer","year":"2017","unstructured":"F\u00fcrer, M.: On the combinatorial power of the Weisfeiler-Lehman algorithm. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) CIAC 2017. LNCS, vol. 10236, pp. 260\u2013271. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57586-5_22"},{"issue":"5","key":"17_CR13","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/2371656.2371662","volume":"59","author":"M Grohe","year":"2012","unstructured":"Grohe, M.: Fixed-point definability and polynomial time on graphs with excluded minors. J. ACM 59(5), 27:1-27:64 (2012). https:\/\/doi.org\/10.1145\/2371656.2371662","journal-title":"J. ACM"},{"key":"17_CR14","doi-asserted-by":"publisher","unstructured":"Immerman, N., Lander, E.: Describing graphs: a first-order approach to graph canonization. In: Selman, A.L. (eds) Complexity Theory Retrospective. Springer, New York, NY (1990). https:\/\/doi.org\/10.1007\/978-1-4612-4478-3_5","DOI":"10.1007\/978-1-4612-4478-3_5"},{"issue":"6","key":"17_CR15","doi-asserted-by":"publisher","first-page":"44:1","DOI":"10.1145\/3333003","volume":"66","author":"S Kiefer","year":"2019","unstructured":"Kiefer, S., Ponomarenko, I., Schweitzer, P.: The Weisfeiler-Leman dimension of planar graphs is at most 3. J. ACM 66(6), 44:1-44:31 (2019). https:\/\/doi.org\/10.1145\/3333003","journal-title":"J. ACM"},{"issue":"1","key":"17_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.26493\/1855-3974.121.885","volume":"5","author":"M Muzychuk","year":"2012","unstructured":"Muzychuk, M., Ponomarenko, I.: On pseudocyclic association schemes. ARS Math. Contemp. 5(1), 1\u201325 (2012)","journal-title":"ARS Math. Contemp."},{"key":"17_CR17","doi-asserted-by":"publisher","unstructured":"Muzychuk, M.E., Klin, M.H., P\u00f6schel, R.: The isomorphism problem for circulant graphs via Schur ring theory. In: Codes and Association Schemes. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 56, pp. 241\u2013264. DIMACS\/AMS (1999). https:\/\/doi.org\/10.1090\/dimacs\/056\/19","DOI":"10.1090\/dimacs\/056\/19"},{"key":"17_CR18","unstructured":"Muzychuk, M.E., Tinhofer, G.: Recognizing circulant graphs of prime order in polynomial time. Electr. J. Comb. 5 (1998). http:\/\/www.combinatorics.org\/Volume_5\/Abstracts\/v5i1r25.html"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/S0021-9800(67)80003-6","volume":"3","author":"J Turner","year":"1967","unstructured":"Turner, J.: Point-symmetric graphs with a prime number of points. J. Comb. Theory 3, 136\u2013145 (1967)","journal-title":"J. Comb. Theory"},{"key":"17_CR20","unstructured":"Weisfeiler, B., Leman, A.: The reduction of a graph to canonical form and the algebra which appears therein. NTI Ser. 2(9), 12\u201316 (1968). https:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-75242-2_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T09:47:29Z","timestamp":1672048049000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-75242-2_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030752415","9783030752422"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-75242-2_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"4 May 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 May 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 May 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/easyconferences.eu\/ciac2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"78","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"27","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the Corona pandemic the conference was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}