{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T02:19:31Z","timestamp":1773368371287,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540744559","type":"print"},{"value":"9783540744566","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74456-6_51","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"572-583","source":"Crossref","is-referenced-by-count":2,"title":["Hardness Results for Tournament Isomorphism and Automorphism"],"prefix":"10.1007","author":[{"given":"Fabian","family":"Wagner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"51_CR1","doi-asserted-by":"crossref","unstructured":"Arvind, V., Beigel, R., Lozano, A.: The Complexity of Modular Graph Automorphism. Symp. on Theoret. Aspects of Computer Sci., 172\u2013182 (1998)","DOI":"10.1007\/BFb0028559"},{"key":"51_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/11940128_46","volume-title":"Algorithms and Computation","author":"V. Arvind","year":"2006","unstructured":"Arvind, V., Das, B., Mukhopadhyay, P.: On Isomorphism and Canonization of Tournaments and Hypertournaments. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 449\u2013459. Springer, Heidelberg (2006)"},{"key":"51_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1051\/ita\/1996300100011","volume":"30","author":"E. Allender","year":"1996","unstructured":"Allender, E., Ogihara, M.: Relationships among PL, and the determinant. RAIRO Inform. Theor. Appl.\u00a030, 1\u201321 (1996)","journal-title":"RAIRO Inform. Theor. Appl."},{"key":"51_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"C. Alvarez","year":"1993","unstructured":"Alvarez, C., Jenner, B.: A very hard logspace counting class. Theoretical Computer Science\u00a0107, 3\u201330 (1993)","journal-title":"Theoretical Computer Science"},{"key":"51_CR5","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D.A.M. Barrington","year":"1990","unstructured":"Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC1. J. Comput. System Sci.\u00a041, 274\u2013306 (1990)","journal-title":"J. Comput. System Sci."},{"key":"51_CR6","doi-asserted-by":"crossref","unstructured":"Babai, L., Luks, E.: Canonical labeling of graphs. Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 171\u2013183 (1983)","DOI":"10.1145\/800061.808746"},{"key":"51_CR7","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. Boppana","year":"1987","unstructured":"Boppana, R., Hastad, J., Zachos, S.: Does co-NP have short interactive proofs? Inform. Process. Lett.\u00a025, 27\u201332 (1987)","journal-title":"Inform. Process. Lett."},{"key":"51_CR8","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF01374526","volume":"25","author":"G. Buntrock","year":"1992","unstructured":"Buntrock, G., Damm, C., Hertrampf, U., Meinel, C.: Structure and importance of logspace-MOD-classes. Math. System Theory\u00a025, 223\u2013237 (1992)","journal-title":"Math. System Theory"},{"key":"51_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/3-540-63385-5_30","volume-title":"Computational Logic and Proof Theory","author":"S.R. Buss","year":"1997","unstructured":"Buss, S.R.: Alogtime algorithms for tree isomorphism, comparison, and canonization. In: Gottlob, G., Leitsch, A., Mundici, D. (eds.) KGC 1997. LNCS, vol.\u00a01289, pp. 18\u201333. Springer, Heidelberg (1997)"},{"key":"51_CR10","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"Cook, S.A.: A taxonomy of problems with fast parallel algorithms. Information and Control\u00a064, 2\u201322 (1985)","journal-title":"Information and Control"},{"key":"51_CR11","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J.: Computational complexity of probabilistic Turing machines. SIAM J. Comput.\u00a06, 675\u2013695 (1977)","journal-title":"SIAM J. Comput."},{"key":"51_CR12","doi-asserted-by":"crossref","unstructured":"Gross, J.L., Yellen, J.: Discrete Mathematics and its Applications - Handbook of Graph Theory. CRC Press LLC (2004)","DOI":"10.1201\/9781420057140"},{"key":"51_CR13","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Tarjan, R.E.: A V 2 algorithm for determining isomorphism of planar graphs, pp. 32\u201334 (1971)","DOI":"10.1016\/0020-0190(71)90019-6"},{"key":"51_CR14","doi-asserted-by":"crossref","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The Graph Isomorphism Problem - Its Structural Complexity. In: Prog. Theor. Comp.Sci., Birkhaeuser, Boston, MA (1993)","DOI":"10.1007\/978-1-4612-0333-9"},{"key":"51_CR15","doi-asserted-by":"crossref","unstructured":"Lindell, S.: A logspace algorithm for tree canonization. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pp. 400\u2013404 (1992)","DOI":"10.1145\/129712.129750"},{"key":"51_CR16","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"E. Luks","year":"1982","unstructured":"Luks, E.: Isomorphism of bounded valence can be tested in polynomial time. J. Comput. System Sci.\u00a025, 42\u201365 (1982)","journal-title":"J. Comput. System Sci."},{"key":"51_CR17","doi-asserted-by":"crossref","unstructured":"Luks, E.: Parallel algorithms for perumtation groups and graph isomorphism. In: Proc. of the 27th IEEE Symp. on Found. of Comp. Sci., pp. 292\u2013302 (1986)","DOI":"10.1109\/SFCS.1986.39"},{"issue":"6","key":"51_CR18","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1137\/0220070","volume":"20","author":"G.L. Miller","year":"1991","unstructured":"Miller, G.L., Reif, J.H.: Parallel tree contraction Part 2: further applications. SIAM Journal on Computing\u00a020(6), 1128\u20131147 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"51_CR19","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0022-0000(84)90066-7","volume":"28","author":"W. Ruzzo","year":"1984","unstructured":"Ruzzo, W., Simon, J., Tompa, M.: Space bounded hierarchies and probabilistic computations. J. Comput. System Sci.\u00a028, 216\u2013230 (1984)","journal-title":"J. Comput. System Sci."},{"key":"51_CR20","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. Comput. System Sci.\u00a037, 312\u2013323 (1988)","journal-title":"J. Comput. System Sci."},{"issue":"5","key":"51_CR21","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(5), 1093\u20131108 (2004)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,21]],"date-time":"2021-08-21T18:10:24Z","timestamp":1629569424000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}