{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:37:40Z","timestamp":1762101460855},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_13","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"145-156","source":"Crossref","is-referenced-by-count":12,"title":["Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement"],"prefix":"10.1007","author":[{"given":"Christoph","family":"Berkholz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Bonsma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Babai, L.: Moderately exponential bound for graph isomorphism. In: G\u00e9cseg, F. (ed.) FCT 1981. LNCS, vol.\u00a0117, pp. 34\u201350. Springer, Heidelberg (1981)","DOI":"10.1007\/3-540-10854-8_4"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1137\/0209047","volume":"9","author":"L. Babai","year":"1980","unstructured":"Babai, L., Erd\u00f6s, P., Selkow, S.: Random graph isomorphism. SIAM Journal on Computing\u00a09, 628\u2013635 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Babai, L., Luks, E.: Canonical labeling of graphs. In: Proc. STOC 1983, pp. 171\u2013183 (1983)","DOI":"10.1145\/800061.808746"},{"issue":"4","key":"13_CR4","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\u00a012(4), 389\u2013410 (1992)","journal-title":"Combinatorica"},{"issue":"1","key":"13_CR5","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(82)90016-0","volume":"19","author":"A. Cardon","year":"1982","unstructured":"Cardon, A., Crochemore, M.: Partitioning a graph in O(|A|log2|V|). Theoretical Computer Science\u00a019(1), 85\u201398 (1982)","journal-title":"Theoretical Computer Science"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Darga, P., Liffiton, M., Sakallah, K., Markov, I.: Exploiting structure in symmetry detection for CNF. In: Proc. DAG 2004, pp. 530\u2013534 (2004)","DOI":"10.1145\/996566.996712"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.: An n log n algorithm for minimizing states in a finite automaton. In: Kohavi, Z., Paz, A. (eds.) Theory of Machines and Computations, pp. 189\u2013196. Academic Press (1971)","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Junttila, T., Kaski, P.: Engineering an efficient canonical labeling tool for large and sparse graphs. In: Proc. ALENEX 2007, pp. 135\u2013149 (2007)","DOI":"10.1137\/1.9781611972870.13"},{"key":"13_CR9","first-page":"45","volume":"30","author":"B. McKay","year":"1981","unstructured":"McKay, B.: Practical graph isomorphism. Congressus Numerantium\u00a030, 45\u201387 (1981)","journal-title":"Congressus Numerantium"},{"key":"13_CR10","unstructured":"McKay, B.: Nauty users guide (version 2.4). Computer Science Dept., Australian National University (2007)"},{"issue":"6","key":"13_CR11","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.: Three partition refinement algorithms. SIAM Journal on Computing\u00a016(6), 973\u2013989 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"13_CR12","unstructured":"Piperno, A.: Search space contraction in canonical labeling of graphs. arXiv preprint arXiv:0804.4881v2 (2011)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T12:50:42Z","timestamp":1558011042000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}