{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:10:44Z","timestamp":1710342644001},"reference-count":17,"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":[[2014,4]]},"abstract":"<jats:p> In this paper, we investigate the problem of computing structural sensitive variations of an unordered tree edit distance. First, we focus on the variations tractable by the algorithms including the submodule of a network algorithm, either the minimum cost maximum flow algorithm or the maximum weighted bipartite matching algorithm. Then, we show that both network algorithms are replaceable, and hence the time complexity of computing these variations can be reduced to O(nmd) time, where n is the number of nodes in a tree, m is the number of nodes in another tree and d is the minimum degree of given two trees. Next, we show that the problem of computing the bottom-up distance is MAX SNP-hard. Note that the well-known linear-time algorithm for the bottom-up distance designed by Valiente (2001) computes just a bottom-up indel (insertion-deletion) distance allowing no substitutions. <\/jats:p>","DOI":"10.1142\/s0129054114500154","type":"journal-article","created":{"date-parts":[[2014,7,25]],"date-time":"2014-07-25T01:48:52Z","timestamp":1406252932000},"page":"307-329","source":"Crossref","is-referenced-by-count":8,"title":["TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE"],"prefix":"10.1142","volume":"25","author":[{"given":"YOSHIYUKI","family":"YAMAMOTO","sequence":"first","affiliation":[{"name":"Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KOUICHI","family":"HIRATA","sequence":"additional","affiliation":[{"name":"Department of Artificial Intelligence and Biomedical Informatics R&amp;D Center, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TETSUJI","family":"KUBOYAMA","sequence":"additional","affiliation":[{"name":"Computer Center, Gakushuin University, Mejiro 1-5-1, Toshima, Tokyo 171-8588, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2014,7,24]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.11.017"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1051\/forest:2000134"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1137\/0218069"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21458-5_34"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90246-E"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1979.6786615"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90064-3"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322143"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-009-0059-3"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(99)00199-5"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(94)00109-Y"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01975866"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1137\/0218082"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90062-0"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90136-J"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054196000051"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114500154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:54:31Z","timestamp":1565186071000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114500154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4]]},"references-count":17,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2014,7,24]]},"published-print":{"date-parts":[[2014,4]]}},"alternative-id":["10.1142\/S0129054114500154"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114500154","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4]]}}}