{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:40:09Z","timestamp":1742593209965,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540534877"},{"type":"electronic","value":"9783540463139"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-53487-3_45","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:06:07Z","timestamp":1330207567000},"page":"204-214","source":"Crossref","is-referenced-by-count":1,"title":["Optimal parallel algorithms for testing isomorphism of trees and outerplanar graphs"],"prefix":"10.1007","author":[{"given":"Christos","family":"Levcopoulos","sequence":"first","affiliation":[]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[]},{"given":"Ola","family":"Petersson","sequence":"additional","affiliation":[]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K. Abrahamson","year":"1989","unstructured":"K. Abrahamson, N. Dadoun, D. Kirkpatrick, T. Przytycka, \u201dA simple tree contraction method\u201d, Journal of Algorithms 10, 1989, 287\u2013302","journal-title":"Journal of Algorithms"},{"key":"15_CR2","volume-title":"The design and analysis of computer algorithms","author":"A. Aho","year":"1984","unstructured":"A. Aho, J. Hopcroft, J. Ullman, \u201dThe design and analysis of computer algorithms\u201d, Addison-Weley, Reading, 1984"},{"key":"15_CR3","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/3-540-19487-8_26","volume":"318","author":"H. Bodlaender","year":"1988","unstructured":"H. Bodlaender, \u201dPolynomial algorithms for graph isomorphism and chromatic index on partial k-trees\u201d, in SWAT'88, Lect.Notes in Com.Science 318, 223\u2013232, 1988","journal-title":"SWAT'88, Lect.Notes in Com.Science"},{"key":"15_CR4","unstructured":"B.Chlebus, K.Diks, T.Radzik, \u201dTesting isomorphism of outerplanar graphs in parallel\u201d, in MFCS'88, Lect.Notes in Comp.Science, 1988"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"H.Gazit, J.Reif, \u201dA randomized parallel algorithm for planar graph isomorphism\u201d, SPAA'90,210\u2013219.","DOI":"10.1145\/97444.97687"},{"key":"15_CR6","unstructured":"A.Gibbons, W.Rytter, \u201dEfficient parallel algorithms\u201d, Cambridge University Press"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"A.Gibbons, W.Rytter, \u201dOptimal parallel evaluation of expressions and applications to context-free recognition\u201d, Information and Computation, 1989","DOI":"10.1016\/0890-5401(89)90027-8"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"P.Gibbons, R.Karp, G.Miller, D.Soroker, \u201dSubtree isomorphism is in random NC\u201d, AWOC'88, 43\u201352","DOI":"10.1007\/BFb0040372"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"K.Diks, T.Hagerup, W.Rytter, \u201dOptimal parallel recognition and colouring of outerplanar graphs\u201d, MFCS'89, Lect.Notes in Comp.Science, 1989","DOI":"10.1007\/3-540-51486-4_68"},{"key":"15_CR10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0020-0190(89)90170-1","volume":"30","author":"A. Lingas","year":"1989","unstructured":"A. Lingas, M. Karpinski, \u201dSubtree isomorphism is NC reducible to bipartite perfect matching\u201d, IPL 30, 1989, 27\u201332","journal-title":"IPL"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"E.M. Luks,.\u201dIsomorphism of bounded valence can be tested in polynomial time\u201d, in Proc. 21st Ann. Symp. of Foundations of Computer Science (IEEE, New York, 1980).","DOI":"10.1109\/SFCS.1980.24"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"G.Miller, J.Reif, \u201dParallel tree contraction and its application\u201d, FOCS, 1985","DOI":"10.1109\/SFCS.1985.43"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"J H Reif, \u201dAn optimal parallel algorithm for integer sorting\u201d, Proc. 26th Ann. Symp. on Foundations of Computer Science, 1985.","DOI":"10.1109\/SFCS.1985.9"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"W.L.Ruzzo, \u201dOn uniform circuit complexity\u201d, JCSS 22, 1981","DOI":"10.1016\/0022-0000(81)90038-6"},{"key":"15_CR15","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. Tarjan","year":"1985","unstructured":"R. Tarjan, U. Vishkin, \u201dAn efficient parallel biconnectivity algorithm\u201d, SIAM J.Comp. 14, 1985, 862\u2013874","journal-title":"SIAM J.Comp."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-53487-3_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:08:41Z","timestamp":1742591321000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-53487-3_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540534877","9783540463139"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-53487-3_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}