{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:32Z","timestamp":1725664172046},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_91","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:59:08Z","timestamp":1330257548000},"page":"397-408","source":"Crossref","is-referenced-by-count":1,"title":["Finding largest common embeddable subtrees"],"prefix":"10.1007","author":[{"given":"Arvind","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naomi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"35_CR1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(92)90132-Y","volume":"92","author":"A. Apostolico","year":"1992","unstructured":"A. Apostolico, S. Browne and C. Guerra, Fast linear-space computations of longest common subsequence, Theoretical Computer Science 92 (1992), pp. 3\u201317.","journal-title":"Theoretical Computer Science"},{"key":"35_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00263499","volume":"27","author":"H. Alblas","year":"1989","unstructured":"H. Alblas, Iteration of transformation passes over attributed program trees, Acta-Informatica 27 (1989), pp. 1\u201340.","journal-title":"Acta-Informatica"},{"issue":"2","key":"35_CR3","doi-asserted-by":"crossref","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, Journal of the ACM 21, 2 (1974), pp. 201\u2013206.","journal-title":"Journal of the ACM"},{"key":"35_CR4","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/0196-6774(87)90030-7","volume":"8","author":"M. J. Chung","year":"1987","unstructured":"M. J. Chung, O(n 2.5) time algorithms for the subgraph homeomorphism problem on trees, Journal of Algorithms 8, (1987), pp. 106\u2013112.","journal-title":"Journal of Algorithms"},{"key":"35_CR5","unstructured":"S. Cook, A. Gupta, and V. Ramachandran, A fast parallel algorithm for formula evaluation, unpublished manuscript, October 1986."},{"key":"35_CR6","unstructured":"M. Farach and M. Thorup, Fast Comparison of evolutionary trees, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 481\u2013488, 1984."},{"key":"35_CR7","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01908078","volume":"2","author":"C.R. Finden","year":"1985","unstructured":"C.R. Finden and A.D. Gordon, Obtaining common pruned trees, Journal of Classification 2, (1985), pp. 255\u2013276.","journal-title":"Journal of Classification"},{"key":"35_CR8","first-page":"113","volume-title":"Formal methods in the study of language, Part I","author":"J. Friedman","year":"1981","unstructured":"J. Friedman, Expressing logical formulas in natural language. Formal methods in the study of language, Part I, Math. Centrum, Amsterdam, 1981, pp. 113\u2013130."},{"issue":"5","key":"35_CR9","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"H. Gabow","year":"1989","unstructured":"H. Gabow and R. Tarjan, Faster scaling algorithms for network problems, SIAM Journal on Computing 18, 5 (1989), pp. 1013\u20131036.","journal-title":"SIAM Journal on Computing"},{"key":"35_CR10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0166-218X(90)90081-M","volume":"29","author":"P. Gibbons","year":"1990","unstructured":"P. Gibbons, R. Karp, G. Miller, AND D. Soroker, Subtree isomorphism is in random NC, Discrete Applied Mathematics 29 (1990), pp. 35\u201362.","journal-title":"Discrete Applied Mathematics"},{"key":"35_CR11","unstructured":"A. Gupta, A fast parallel algorithm for recognition of parenthesis languages, Master's thesis, University of Toronto, 1985."},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"A. Gupta and N. Nishimura, The parallel complexity of tree embedding problems, to appear in Journal of Algorithms. A preliminary version has appeared in Proceedings of the Ninth Annual Symposium on Theoretical Aspects of Computer Science, pp. 21\u201332, 1992.","DOI":"10.1007\/3-540-55210-3_170"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"A. Gupta and N. Nishimura, Sequential and parallel algorithms for embedding problems on classes of partial k-trees, Proceedings of the Fourth Scandinavian Workshop on Algorithm Theory, pp. 172\u2013182, 1994.","DOI":"10.1007\/3-540-58218-5_16"},{"issue":"1","key":"35_CR14","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R. Karp","year":"1986","unstructured":"R. Karp, E. Upfal, and A. Wigderson, Constructing a perfect matching is in random NC, Combinatorica 6, 1, pp. 35\u201348, 1986.","journal-title":"Combinatorica"},{"key":"35_CR15","unstructured":"P. Kilpelainen, Tree matching problems with applications to structured text databases, Ph.D. thesis, University of Helsinki, Department of Computer Science, November 1992."},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"P. Kilpelainen and H. Mannila, Grammatical tree matching, Combinatorial Pattern Matching, 1992.","DOI":"10.1007\/3-540-56024-6_13"},{"key":"35_CR17","first-page":"217","volume":"88","author":"E. Kubicka","year":"1992","unstructured":"E. Kubicka, G. Kubicki, and F.R. McMorris, On agreement subtrees of 2 binary trees, Congressus-Numerantium 88 (1992), pp. 217\u2013224.","journal-title":"Congressus-Numerantium"},{"key":"35_CR18","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 and M. Karpinski, Subtree isomorphism is NC reducible to bipartite perfect matching, Information Processing Letters 30 (1989), pp. 27\u201332.","journal-title":"Information Processing Letters"},{"key":"35_CR19","first-page":"5","volume":"43","author":"P. Materna","year":"1985","unstructured":"P. Materna, P. Sgall and Z. Hajicova, Linguistic constructions in transparent intensional logic, Prague-Bulletin on Mathematical Linguistics 43 (1985), pp. 5\u201324.","journal-title":"Prague-Bulletin on Mathematical Linguistics"},{"key":"35_CR20","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0167-5060(08)70324-8","volume":"2","author":"D. Matula","year":"1978","unstructured":"D. Matula, Subtree isomorphism in O(n 5\/2), Annals of Discrete Mathematics 2 (1978), pp. 91\u2013106.","journal-title":"Annals of Discrete Mathematics"},{"key":"35_CR21","unstructured":"Complexity of optimal vector code generation, Theoretical Computer Science 80 (1991), pp. 105\u2013115."},{"key":"35_CR22","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"N. Robertson and P. Seymour, Graph Minors III. Planar tree-width, Journal of Combinatorial Theory (Ser. B) 36 (1984), pp. 49\u201364.","journal-title":"Journal of Combinatorial Theory (Ser. B)"},{"key":"35_CR23","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P. Seymour, Graph Minors II. Algorithm aspects of treewidth, Journal of Algorithms 7 (1986), pp. 309\u2013322.","journal-title":"Journal of Algorithms"},{"key":"35_CR24","unstructured":"M. Steel and T. Warnow, Kaikoura tree theorems: Computing the maximum agreement subtrees. Submitted for publication."}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_91.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:25:16Z","timestamp":1605630316000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_91"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_91","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}