{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T00:12:03Z","timestamp":1648944723161},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p> We present fast algorithms for computing the largest common subtree (LCST) and for computing the optimal alignment when two similar unordered trees are given. For the LCST problem for rooted trees, we present an O(4<jats:sup>K<\/jats:sup>n) time algorithm, where n is the maximum size of two input trees and the total number of non-common nodes is bounded by K. We extend this algorithm for unrooted trees and obtain an O(K4<jats:sup>K<\/jats:sup>n) time algorithm. Both of these are subquadratic for two similar trees within K = o( log <jats:sub>4<\/jats:sub> n) differences. We also show that the alignment problem for rooted and unordered trees of bounded degree can be solved in O(\u03b3<jats:sup>K<\/jats:sup>n) time for a constant \u03b3. Particularly \u03b3 is at most 4.45 for unlabeled binary trees. <\/jats:p>","DOI":"10.1142\/s0129054106004054","type":"journal-article","created":{"date-parts":[[2006,6,6]],"date-time":"2006-06-06T07:11:37Z","timestamp":1149577897000},"page":"703-729","source":"Crossref","is-referenced-by-count":2,"title":["FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES"],"prefix":"10.1142","volume":"17","author":[{"given":"DAIJI","family":"FUKAGAWA","sequence":"first","affiliation":[{"name":"Department of Intelligence Science and Technology, Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto, 606\u20138501, Japan"}]},{"given":"TATSUYA","family":"AKUTSU","sequence":"additional","affiliation":[{"name":"Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto, 611\u20130011, Japan"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974"},{"key":"rf2","first-page":"1488","volume":"76","author":"Akutsu T.","journal-title":"IEICE Trans. on Information and Systems E"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00278-8"},{"key":"rf4","first-page":"134","volume":"14","author":"Aoki K. F.","journal-title":"Genome Informatics"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkh473"},{"key":"rf6","volume-title":"Computational Molecular Biology: An Introduction","author":"Clote P.","year":"2000"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382704"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00054-X"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90198-3"},{"key":"rf10","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"Harary F.","year":"1969"},{"key":"rf12","first-page":"105","volume":"56","author":"Jansson J.","journal-title":"Fundamenta Informaticae"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)80029-9"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90010-2"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70324-8"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021271615909"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1044"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90011-3"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322143"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04921-1"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01975866"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90062-0"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1137\/0218082"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054106004054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:28:30Z","timestamp":1565177310000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054106004054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":22,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1142\/S0129054106004054"],"URL":"https:\/\/doi.org\/10.1142\/s0129054106004054","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}