{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:39:01Z","timestamp":1787506741675,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540359043","type":"print"},{"value":"9783540359050","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_2","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T06:46:45Z","timestamp":1151477205000},"page":"3-14","source":"Crossref","is-referenced-by-count":29,"title":["Testing Graph Isomorphism in Parallel by Playing a Game"],"prefix":"10.1007","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oleg","family":"Verbitsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"2_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/3-540-10854-8_4","volume-title":"Fundamentals of Computation Theory","author":"L. Babai","year":"1981","unstructured":"Babai, L.: Moderately exponential bound for graph isomorphism. In: Gecseg, F. (ed.) FCT 1981. LNCS, vol.\u00a0117, pp. 34\u201350. Springer, Heidelberg (1981)"},{"key":"2_CR2","first-page":"1447","volume-title":"Handbook of Combinatorics, Ch. 27","author":"L. Babai","year":"1995","unstructured":"Babai, L.: Automorphism groups, isomorphism, reconstruction. In: Graham, R.L., Gr\u00f6tschel, M., Lov\u00e1sz, L. (eds.) Handbook of Combinatorics, Ch. 27, pp. 1447\u20131540. Elsevier Publ., Amsterdam (1995)"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Babai, L., Grigoryev, D., Yu., M.D.M.: Isomorphism of graphs with bounded eigenvalue multiplicity. In: Proc. of the 14th ACM Symp. on Theory of Computing, pp. 310\u2013324 (1982)","DOI":"10.1145\/800070.802206"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L., Luks, E.M.: Canonical labeling of graphs. In: Proc. of the 15th ACM Symposium on Theory of Computing, pp. 171\u2013183 (1983)","DOI":"10.1145\/800061.808746"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"H.L. Bodlaender","year":"1990","unstructured":"Bodlaender, H.L.: Polynomial algorithms for Graph Isomorphism and Chromatic Index on partial k-trees. J. Algorithms\u00a011, 631\u2013643 (1990)","journal-title":"J. Algorithms"},{"key":"2_CR6","unstructured":"Bohman, T., Frieze, A.: \u0141uczak, T., Pikhurko, O., Smyth, C., Spencer, J., Verbitsky, O.: The first order definability of trees and sparse random graphs. E-print (2005), http:\/\/arxiv.org\/abs\/math.CO\/0506288"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R.B. Boppana","year":"1987","unstructured":"Boppana, R.B., Stad, H.J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett.\u00a025, 127\u2013132 (1987)","journal-title":"Inf. Process. Lett."},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J.-Y. Cai","year":"1992","unstructured":"Cai, J.-Y., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica\u00a012, 389\u2013410 (1992)","journal-title":"Combinatorica"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0020-0190(90)90011-L","volume":"34","author":"N. Chandrasekharan","year":"1990","unstructured":"Chandrasekharan, N.: Isomorphism testing of k-trees is in NC, for fixed k. Inf. Process. Lett.\u00a034, 283\u2013287 (1990)","journal-title":"Inf. Process. Lett."},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s00453-001-0052-4","volume":"32","author":"J.G. Greco Del","year":"2002","unstructured":"Del Greco, J.G., Sekharan, C.N., Sridhar, R.: Fast parallel reordering and isomorphism testing of k-trees. Algorithmica\u00a032, 61\u201372 (2002)","journal-title":"Algorithmica"},{"key":"2_CR11","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1023\/A:1018672019177","volume":"10","author":"S. Evdokimov","year":"1999","unstructured":"Evdokimov, S., Karpinski, M., Ponomarenko, I.: On a new high dimensional Weisfeiler-Lehman algorithm. J. Algebraic Combinatorics\u00a010, 29\u201345 (1999)","journal-title":"J. Algebraic Combinatorics"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Evdokimov, S., Ponomarenko, I.: On highly closed cellular algebras and highly closed isomorphism. In: Electronic J. Combinatorics, vol.\u00a06 (1999) #R18","DOI":"10.37236\/1450"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Filotti, I.S., Mayer, J.N.: A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. In: Proc. of the 12th ACM Symp. on Theory of Computing, pp. 236\u2013243 (1980)","DOI":"10.1145\/800141.804671"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Fixed-point logics on planar graphs. In: Proc. of the Ann. Conf. on Logic in Computer Science, pp. 6\u201315 (1998)","DOI":"10.1109\/LICS.1998.705639"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Isomorphism testing for embeddable graphs through definability. In: Proc. of the 32nd ACM Ann. Symp. on Theory of Computing, pp. 63\u201372 (2000)","DOI":"10.1145\/335305.335313"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-49257-7_6","volume-title":"Database Theory - ICDT\u201999","author":"M. Grohe","year":"1998","unstructured":"Grohe, M., Marino, J.: Definability and descriptive complexity on databases of bounded tree-width. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, pp. 70\u201382. Springer, Heidelberg (1998)"},{"key":"2_CR17","unstructured":"Grohe, M., Verbitsky, O.: Testing graph isomorphism in parallel by playing a game. E-print (2006), http:\/\/arxiv.org\/abs\/cs.CC\/0603054"},{"key":"2_CR18","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/978-1-4684-2001-2_13","volume-title":"Complexity of computer computations","author":"J.E. Hopcroft","year":"1972","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Isomorphism of planar graphs (working paper). In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of computer computations, pp. 131\u2013152. Plenum Press, New York (1972)"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Wong, J.K.: Linear time algorithm for isomorphism of planar graphs. In: Proc. of the 6th ACM Symp. on Theory of Computing, pp. 172\u2013184 (1974)","DOI":"10.1145\/800119.803896"},{"key":"2_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive complexity. Springer, Heidelberg (1999)"},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/S0022-0000(03)00042-4","volume":"66","author":"B. Jenner","year":"2003","unstructured":"Jenner, B., K\u00f6bler, J., McKenzie, P., Tor\u00e1n, J.: Completeness Results for Graph Isomorphism. J.\u00a0Comput. Syst. Sci.\u00a066, 549\u2013566 (2003)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"2_CR22","first-page":"869","volume-title":"Algorithms and complexity. Handbook of theoretical computer science","author":"R.M. Karp","year":"1990","unstructured":"Karp, R.M., Ramachandran, V.: Parallel algorithms for shared-memory machines. In: van Leeuwen, J. (ed.) Algorithms and complexity. Handbook of theoretical computer science, pp. 869\u2013941. Elsevier Publ., Amsterdam (1990)"},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Kim, J.-H., Pikhurko, O., Spencer, J., Verbitsky, O.: How complex are random graphs in first order logic? In: Random Structures and Algorithms, vol.\u00a026, pp. 119\u2013145 (2005)","DOI":"10.1002\/rsa.20049"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Lindell, S.: A logspace algorithm for tree canonization. In: Proc. of the 24th Ann. ACM Symp. on Theory of Computing, pp. 400\u2013404 (1992)","DOI":"10.1145\/129712.129750"},{"key":"2_CR25","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"E.M. Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J.\u00a0Comput. Syst. Sci. 25 (1982) 42\u201365","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"Miller, G.L.: Isomorphism testing for graphs of bounded genus. In: Proc. of the 12th ACM Symp. on Theory of Computing, pp. 225\u2013235 (1980)","DOI":"10.1145\/800141.804670"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Reif, J.H.: Parallel tree contraction. Part 2: further applications. SIAM J. Comput.\u00a020, 1128\u20131147","DOI":"10.1137\/0220070"},{"key":"2_CR28","doi-asserted-by":"crossref","unstructured":"Mohar, B., Thomassen, C.: Graphs on surfaces. The John Hopkins University Press (2001)","DOI":"10.56021\/9780801866890"},{"key":"2_CR29","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.apal.2005.04.003","volume":"139","author":"O. Pikhurko","year":"2006","unstructured":"Pikhurko, O., Spencer, J., Verbitsky, O.: Succinct definitions in first order graph theory. Annals of Pure and Applied Logic\u00a0139, 74\u2013109 (2006)","journal-title":"Annals of Pure and Applied Logic"},{"key":"2_CR30","unstructured":"Pikhurko, O., Veith, H., Verbitsky, O.: First order definability of graphs: tight bounds on quantifier rank. Discrete Applied Mathematics (to appear)"},{"key":"2_CR31","first-page":"147","volume":"174","author":"I.N. Ponomarenko","year":"1988","unstructured":"Ponomarenko, I.N.: The isomorphism problem for classes of graphs that are invariant with respect to contraction. Computational Complexity Theory 3. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov\u00a0174, 147\u2013177 (1988)","journal-title":"Computational Complexity Theory 3. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov"},{"key":"2_CR32","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/S0022-0000(05)80070-4","volume":"49","author":"V. Ramachandran","year":"1994","unstructured":"Ramachandran, V., Reif, J.: Planarity testing in parallel. J.Comput.Syst.Sci.\u00a049, 517\u2013561 (1994)","journal-title":"J.Comput.Syst.Sci."},{"key":"2_CR33","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors II. Algorithmic aspects of tree-width. J.Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"J.Algorithms"},{"key":"2_CR34","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U. Sch\u00f6ning","year":"1988","unstructured":"Sch\u00f6ning, U.: Graph isomorphism is in the low hierarchy. J.\u00a0Comput.Syst.Sci.\u00a037, 312\u2013323 (1988)","journal-title":"J.\u00a0Comput.Syst.Sci."},{"key":"2_CR35","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04538-1","volume-title":"The strange logic of random graphs","author":"J. Spencer","year":"2001","unstructured":"Spencer, J.: The strange logic of random graphs. Springer, Heidelberg (2001)"},{"key":"2_CR36","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1137\/S009753970241096X","volume":"33","author":"J. Tor\u00e1n","year":"2004","unstructured":"Tor\u00e1n, J.: On the hardness of graph isomorphism. SIAM J.Comput.\u00a033, 1093\u20131108 (2004)","journal-title":"SIAM J.Comput."},{"key":"2_CR37","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.tcs.2005.05.003","volume":"343","author":"O. Verbitsky","year":"2005","unstructured":"Verbitsky, O.: The first order definability of graphs with separators via the Ehrenfeucht game. Theor.Comput.Sci.\u00a0343, 158\u2013176 (2005)","journal-title":"Theor.Comput.Sci."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,7]],"date-time":"2023-05-07T17:20:31Z","timestamp":1683480031000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/11786986_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}