{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T19:27:56Z","timestamp":1768678076453,"version":"3.49.0"},"reference-count":27,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2003,5,1]],"date-time":"2003-05-01T00:00:00Z","timestamp":1051747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3766,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,5]]},"DOI":"10.1016\/s0022-0000(03)00042-4","type":"journal-article","created":{"date-parts":[[2003,5,19]],"date-time":"2003-05-19T18:04:16Z","timestamp":1053367456000},"page":"549-566","source":"Crossref","is-referenced-by-count":39,"title":["Completeness results for graph isomorphism"],"prefix":"10.1016","volume":"66","author":[{"given":"Birgit","family":"Jenner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"K\u00f6bler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jacobo","family":"Tor\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(03)00042-4_BIB1","unstructured":"A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"10.1016\/S0022-0000(03)00042-4_BIB2","first-page":"73","article-title":"A compendium of problems complete for symmetric logarithmic space","volume":"9","author":"\u00c1lvarez","year":"2000","journal-title":"J. Comput. Complexity"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB3","doi-asserted-by":"crossref","unstructured":"L. Babai, Monte Carlo algorithms, for graph isomorphism testing, Technical Report 79-10, Dep. Math. Stat., Univ. de Montr\u00e9al, 1979.","DOI":"10.1007\/BF01902606"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB4","doi-asserted-by":"crossref","unstructured":"L. Babai, Moderately exponential bounds for graph isomorphism, in: Proceedings of the International Symposium on Fundamentals of Computing Theory 81, Lecture Notes in Computer Science, Vol. 117, Springer, Berlin, Heidelberg, New York, 1981, pp. 34\u201350.","DOI":"10.1007\/3-540-10854-8_4"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB5","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","article-title":"Bounded-width polynomial-size branching programs recognize exactly those languages in NC1","volume":"38","author":"Barrington","year":"1989","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00042-4_BIB6","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","article-title":"On uniformity within NC1","volume":"41","author":"Barrington","year":"1990","journal-title":"J. Comput. System Sci."},{"issue":"3","key":"10.1016\/S0022-0000(03)00042-4_BIB7","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1006\/jcss.1995.1035","article-title":"Circuits, matrices and nonassociative computation","volume":"50","author":"Beaudry","year":"1995","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00042-4_BIB8","doi-asserted-by":"crossref","unstructured":"S.R. Buss, Algorithms for Boolean formula evaluation and for tree contraction, in: P. Clote and J. Krajicek (Eds.), Proof Theory, Complexity, and Arithmetic, Oxford University Press, 1993, pp. 95\u2013115.","DOI":"10.1093\/oso\/9780198536901.003.0005"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB9","doi-asserted-by":"crossref","unstructured":"S. Buss, Alogtime algorithms for tree isomorphism, comparison, and canonization, in: Computational Logic and Proof Theory, 5th Kurt G\u00f6del Colloquium\u201997, Lecture Notes in Computer Science, Vol. 1289, Springer, Berlin, Heidelberg, New York, 1997, pp. 18\u201333.","DOI":"10.1007\/3-540-63385-5_30"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB10","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/BF01305232","article-title":"An optimal lower bound for the number of variables for graph identification","volume":"12","author":"Cai","year":"1992","journal-title":"Combinatorica"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB11","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF01303054","article-title":"On computing boolean connectives of characteristic functions","volume":"28","author":"Chang","year":"1995","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB12","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","article-title":"Problems complete for deterministic logarithmic space","volume":"8","author":"Cook","year":"1987","journal-title":"J. Algorithms"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB13","doi-asserted-by":"crossref","unstructured":"K. Etessami, Counting quantifiers, successor relations, and logarithmic space, in: Proceedings of the 10th Structure in Complexity Theory Conference, IEEE Computer Society Press, Silver Spring, MD, 1995, pp. 2\u201311.","DOI":"10.1109\/SCT.1995.514723"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB14","doi-asserted-by":"crossref","unstructured":"M. Frust, J. Hopcroft, E. Luks, Polynomial time algorithms for permutations groups, in: Proceedings of the 21st IEEE Symposium on the Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 1980, pp. 36\u201341.","DOI":"10.1109\/SFCS.1980.34"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB15","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/0020-0190(71)90019-6","article-title":"A V2 algorithm for determining isomorphism of planar graphs","volume":"1","author":"Hopcroft","year":"1971","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0022-0000(03)00042-4_BIB16","series-title":"Complexity Theory Retrospective","first-page":"59","article-title":"Describing graphs","author":"Immerman","year":"1990"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB17","doi-asserted-by":"crossref","unstructured":"B. Jenner, P. McKenzie, J. Tor\u00e1n, A note on the hardness of tree isomorphism, in: Proceedings of the 13th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Silver Spring, MD, 1998, pp. 101\u2013106.","DOI":"10.1109\/CCC.1998.694595"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB18","series-title":"The Graph Isomorphism Problem","author":"K\u00f6bler","year":"1993"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB19","doi-asserted-by":"crossref","unstructured":"J. K\u00f6bler, J. Tor\u00e1n, The complexity of graph isomorphism for colored graphs with color classes of size 2 and 3, in: Proceedings of the 19th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 2285, Springer, Berlin, Heidelberg, New York, 2002, pp. 121\u2013132.","DOI":"10.1007\/3-540-45841-7_9"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB20","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0304-3975(82)90058-5","article-title":"Symmetric space-bounded computation","volume":"19","author":"Lewis","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(03)00042-4_BIB21","doi-asserted-by":"crossref","unstructured":"S. Lindell, A logspace algorithm for tree canonization, in: Proceedings of the 24th ACM Symposium on Theory of Computing, ACM Press, New York, 1992, pp. 400\u2013404.","DOI":"10.1145\/129712.129750"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB22","doi-asserted-by":"crossref","unstructured":"A. Lozano, J. Tor\u00e1n, On the nonuniform complexity of the graph isomorphism problem, in: K. Ambos-Spies, S. Homer, U. Sch\u00f6ning (Eds.), Complexity Theory, Current Research, Cambridge University Press, Cambridge, MA, 1993, pp. 245\u2013273, also in: Proceedings of the Seventh Structure in Complexity Theory Conference, June 1992, pp. 118\u2013129.","DOI":"10.1109\/SCT.1992.215387"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB23","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","article-title":"Isomorphism of bounded valence can be tested in polynomial time","volume":"25","author":"Luks","year":"1982","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00042-4_BIB24","doi-asserted-by":"crossref","unstructured":"E. Luks, Parallel algorithms for permutation groups and graph isomorphism, in: Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 1986, pp. 292\u2013302.","DOI":"10.1109\/SFCS.1986.39"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB25","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1137\/0220070","article-title":"Parallel tree contraction part 2","volume":"20","author":"Miller","year":"1991","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(03)00042-4_BIB26","doi-asserted-by":"crossref","unstructured":"N. Nisan, A. Ta-Shma, Symmetric logspace is closed under complement, in: Proceedings of the 27th ACM Symposium on Theory of Computing, ACM Press, New York, 1995, pp. 140\u2013146, appeared also in Chicago J. Theoret. Comput. Sci. 1, 1995.","DOI":"10.1145\/225058.225101"},{"key":"10.1016\/S0022-0000(03)00042-4_BIB27","doi-asserted-by":"crossref","unstructured":"J. Tor\u00e1n, On the hardness of graph isomorphism, in: Proceedings of the 41st IEEE Symposium on the Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 2000, pp. 180\u2013186.","DOI":"10.1109\/SFCS.2000.892080"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000424?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000424?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T18:00:11Z","timestamp":1734026411000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000424"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,5]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,5]]}},"alternative-id":["S0022000003000424"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00042-4","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,5]]}}}