{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:38:17Z","timestamp":1725467897110},"publisher-location":"Berlin\/Heidelberg","reference-count":9,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"0387968180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0040372","type":"book-chapter","created":{"date-parts":[[2006,8,3]],"date-time":"2006-08-03T00:03:50Z","timestamp":1154563430000},"page":"43-52","source":"Crossref","is-referenced-by-count":3,"title":["Subtree isomorphism is in random NC"],"prefix":"10.1007","author":[{"given":"Phillip B.","family":"Gibbons","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gary L.","family":"Miller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard M.","family":"Karp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Soroker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"A. Borodin, J. von zur Gathen, and J. Hopcroft. Fast parallel matrix and GCD computations. In Proc. of the Symp. on Foundations of Computer Science (FOCS), Oct. 1982.","DOI":"10.1109\/SFCS.1982.17"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R. Brent","year":"1974","unstructured":"R. Brent. The parallel evaluation of general arithmetic expressions. JACM, 21:201\u2013208, 1974.","journal-title":"JACM"},{"key":"5_CR3","doi-asserted-by":"crossref","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"J. Edmonds. Systems of distinct representatives and linear algebra. J. Res. Nat. Bureau of Standards, 71B:241\u2013245, 1967.","journal-title":"J. Res. Nat. Bureau of Standards"},{"key":"5_CR4","unstructured":"A. Lingas and M. Karpinski. Subtree isomorphism and bipartite perfect matching are mutually NC reducible. 1987. submitted for publication."},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0167-5060(08)70324-8","volume":"2","author":"D. W. Matula","year":"1978","unstructured":"D. W. Matula. Subtree isomorphism in O(n\n                        5\/2). Annals of Discrete Mathematics, 2:91\u2013106, 1978.","journal-title":"Annals of Discrete Mathematics"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif. Parallel tree contraction and its applications. In Proc. of the Symp. on Foundations of Computer Science (FOCS), Oct. 1985.","DOI":"10.1109\/SFCS.1985.43"},{"issue":"1","key":"5_CR7","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"K. Mulmuley, U. Vazirani, and V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105\u2013113, 1987.","journal-title":"Combinatorica"},{"issue":"3","key":"5_CR8","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/0020-0190(78)90079-0","volume":"7","author":"F. Preparata","year":"1978","unstructured":"F. Preparata and D. Sarwate. An improved parallel processor bound in fast matrix inversion. Information Processing Letters, 7(3):148\u2013150, 1978.","journal-title":"Information Processing Letters"},{"key":"5_CR9","unstructured":"M. O. Rabin and V. V. Vazirani. Maximum Matchings in General Graphs through Randomization. Technical Report TR-15-84, Aiken Computation Laboratory, Harvard University, Oct. 1984."}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0040372.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:40:10Z","timestamp":1607550010000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0040372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["0387968180"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/bfb0040372","relation":{},"subject":[]}}