{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T01:57:55Z","timestamp":1768701475292,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540422877","type":"print"},{"value":"9783540482246","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_27","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"322-333","source":"Crossref","is-referenced-by-count":16,"title":["Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations"],"prefix":"10.1007","author":[{"given":"Martin","family":"F\u00fcrer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"27_CR1","unstructured":"L. Babai and L. Ku\u010dera, Graph canonization in linear average time, 20th Annual Symposium on Foundations of Computer Science (Long Beach, Ca., USA), IEEE Computer Society Press, October 1979, pp. 39\u201346."},{"issue":"4","key":"27_CR2","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J.-Y. Cai","year":"1992","unstructured":"Jin-Yi Cai, Martin F\u00fcrer, and Neil Immerman, An optimal lower bound on the number of variables for graph identification, Combinatorica 12 (1992), no. 4, 389\u2013410.","journal-title":"Combinatorica"},{"key":"27_CR3","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1960","unstructured":"A. Ehrenfeucht, An application of games to the completeness problem for formalized theories, Fund. Math. 49 (1960\/1961), 129\u2013141.","journal-title":"Fund. Math."},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-94-017-1972-8","volume-title":"Investigations in algebraic theory of combinatorial objects","author":"I. A. Farad\u017eev","year":"1994","unstructured":"I. A. Farad\u017eev, M. H. Klin, and M. E. Muzichuk, Cellular rings and groups of automorphisms of graphs, Investigations in algebraic theory of combinatorial objects, Kluwer Acad. Publ., Dordrecht, 1994, pp. 1\u2013152."},{"key":"27_CR5","unstructured":"Roland Fra\u00efss\u00e9, Sur quelques classifications des syst\u00e9mes de relations, Publ. Sci. Univ. Alger. S\u00e9r. A. 1 (1954), 35\u2013182 (1955)."},{"issue":"4","key":"27_CR6","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/s004939970004","volume":"19","author":"M. Grohe","year":"1999","unstructured":"Martin Grohe, Equivalence in finite-variable logics is complete for polynomial time, Combinatorica 19 (1999), no. 4, 507\u2013532.","journal-title":"Combinatorica"},{"issue":"1","key":"27_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00147398","volume":"4","author":"D. G. Higman","year":"1975","unstructured":"D. G. Higman, Coherent configurations. I. Ordinary representation theory, Geometriae Dedicata 4 (1975), no. 1, 1\u201332.","journal-title":"Geometriae Dedicata"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"N. Immerman and E. S. Lander, Describing graphs: A first-order approach to graph canonization, Alan L. Selman, Editor, Complexity Theory Retrospective, In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, Springer-Verlag, 1991.","DOI":"10.1007\/978-1-4612-4478-3_5"},{"issue":"1","key":"27_CR9","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/0022-0000(82)90011-3","volume":"25","author":"N. Immerman","year":"1982","unstructured":"Neil Immerman, Upper and lower bounds for first order expressibility, Journal of Computer and System Sciences 25 (1982), no. 1, 76\u201398.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"L. Ku\u010dera, Canonical labeling of regular graphs in linear average time, Proceedings of the 28th Annual Symposium on Foundations of Computer Science (Los Angeles, CA) (Ashok K. Chandra, ed.), IEEE Computer Society Press, October 1987, pp. 271\u2013279.","DOI":"10.1109\/SFCS.1987.11"},{"key":"27_CR11","series-title":"Lecture Notes in Mathematics","volume-title":"On construction and identification of graphs","author":"A. Lehman","year":"1976","unstructured":"Boris Weisfeiler (ed.), On construction and identification of graphs, Springer-Verlag, Berlin, 1976, With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler, Lecture Notes in Mathematics, Vol. 558."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T02:28:08Z","timestamp":1556936888000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_27","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}