{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:36:59Z","timestamp":1725482219065},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540667315"},{"type":"electronic","value":"9783540467847"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46784-x_29","type":"book-chapter","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T08:02:55Z","timestamp":1175760175000},"page":"303-312","source":"Crossref","is-referenced-by-count":2,"title":["Finding Smallest Supertrees Under Minor Containment"],"prefix":"10.1007","author":[{"given":"Naomi","family":"Nishimura","sequence":"first","affiliation":[]},{"given":"Prabhakar","family":"Ragde","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"29_CR1","doi-asserted-by":"publisher","first-page":"1656","DOI":"10.1137\/S0097539794269461","volume":"26","author":"A. Amir","year":"1997","unstructured":"A. Amir and D. Keselman. Maximum agreement subtree in a set of evolutionary trees: metrics and efficient algorithms. SIAM Journal on Computing, 26(6):1656\u20131669, December 1997. 304","journal-title":"SIAM Journal on Computing"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"J. A. Bondy and U.S.R. Murty. Graph Theory with Applications. North-Holland, 1976. 304","DOI":"10.1007\/978-1-349-03521-2"},{"key":"29_CR3","doi-asserted-by":"publisher","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:106\u2013112, 1987. 304","journal-title":"Journal of Algorithms"},{"key":"29_CR4","unstructured":"Richard Cole and Ramesh Hariharan. An O(n log n) algorithm for the maximum agreement subtree problem for binary trees. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 323\u2013332, 1996. 304"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"M. Dubiner, Z. Galil, and E. Magen. Faster tree pattern matching. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 145\u2013150, 1990. 304","DOI":"10.1109\/FSCS.1990.89533"},{"key":"29_CR6","unstructured":"P. Duchet. Tree minors. Presentation at AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, 1991 (personal communication, A. Gupta). 304, 305"},{"issue":"6","key":"29_CR7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(95)00110-X","volume":"55","author":"M. Farach","year":"1995","unstructured":"M. Farach, T. Przytycka, and M. Thorup. On the agreement of many trees. Information Processing Letters, 55(6):297\u2013301, 1995. 304","journal-title":"Information Processing Letters"},{"key":"29_CR8","unstructured":"M. Farach and M. Thorup. Fast comparison of evolutionary trees. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 481\u2013488, 1994. 304"},{"issue":"1","key":"29_CR9","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1006\/jagm.1995.1006","volume":"18","author":"A. Gupta","year":"1995","unstructured":"A. Gupta and N. Nishimura. The parallel complexity of tree embedding problems. Journal of Algorithms, 18(1):176\u2013200, 1995. 304, 304, 311","journal-title":"Journal of Algorithms"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/PL00009212","volume":"21","author":"A. Gupta","year":"1998","unstructured":"A. Gupta and N. Nishimura. Finding largest subtrees and smallest supertrees. Algorithmica, 21:183\u2013210, 1998. 304, 304","journal-title":"Algorithmica"},{"key":"29_CR11","unstructured":"A. Gupta, N. Nishimura, A. Proskurowski, and P. Ragde. Embeddings of k-connected graphs of pathwidth k. Manuscript. 311"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"T. Jiang, L. Wang, and K. Zhang. Alignment of trees-an alternative to tree edit. In Combinatorial Pattern Matching, pages 75\u201386, 1994. 304, 304, 304","DOI":"10.1007\/3-540-58094-8_7"},{"issue":"2","key":"29_CR13","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/S0097539791218202","volume":"24","author":"P. Kilpel\u00e4inen","year":"1995","unstructured":"P. Kilpel\u00e4inen and H. Mannila. Ordered and unordered tree inclusion. SIAM Journal on Computing, 24(2):340\u2013356, 1995. 304","journal-title":"SIAM Journal on Computing"},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"S. R. Kosaraju. Efficient tree pattern matching. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 178\u2013183, 1989. 304","DOI":"10.1109\/SFCS.1989.63475"},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"J. Lagergren. The size of an intertwine. In Proceedings of the 23rd International Colloquium on Automata, Languages, and Programming, volume 820 of Lecture Notes in Computer Science, pages 520\u2013531, 1994. 311","DOI":"10.1007\/3-540-58201-0_95"},{"key":"29_CR16","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J. Matou\u0161ek","year":"1992","unstructured":"J. Matou\u0161ek and R. Thomas. On the complexity of finding iso-and other morphisms for partial k-trees. Discrete Mathematics, 108:343\u2013364, 1992. 311","journal-title":"Discrete Mathematics"},{"key":"29_CR17","doi-asserted-by":"publisher","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. Algorithmic aspects of tree-width. Journal of Algorithms, 7:309\u2013322, 1986. 304","journal-title":"Journal of Algorithms"},{"key":"29_CR18","unstructured":"K. Siddiqi, A. Shokoufandeh, S. Dickinson, and S. Zucker. Shock graphs and shape matching. International Journal of Computer Vision, to appear. 303"},{"key":"29_CR19","unstructured":"T. Warnow. Tree compatibility and inferring evolutionary history. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 382\u2013391, 1993. 304, 304, 304"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46784-X_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T23:38:16Z","timestamp":1556321896000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46784-X_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540667315","9783540467847"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-46784-x_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}