{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:00:00Z","timestamp":1777449600074,"version":"3.51.4"},"reference-count":50,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information Sciences"],"published-print":{"date-parts":[[1995,1]]},"DOI":"10.1016\/0020-0255(94)00057-i","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T22:22:57Z","timestamp":1027635777000},"page":"45-74","source":"Crossref","is-referenced-by-count":24,"title":["Algorithms for approximate graph matching"],"prefix":"10.1016","volume":"82","author":[{"given":"Jason T.L.","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kaizhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gung-Wei","family":"Chirn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0020-0255(94)00057-I_BIB1","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1207\/s15516709cog0901_7","article-title":"A learning algorithm for Boltzmann machines","volume":"9","author":"Ackley","year":"1985","journal-title":"Cognitive Sci."},{"key":"10.1016\/0020-0255(94)00057-I_BIB2","series-title":"Data Structures and Algorithms","author":"Aho","year":"1983"},{"key":"10.1016\/0020-0255(94)00057-I_BIB3","series-title":"Optimization by simulated annealing: An experimental evaluation","author":"Aragon","year":"1984"},{"key":"10.1016\/0020-0255(94)00057-I_BIB4","series-title":"Syntactic Pattern Recognition and Applications","author":"Fu","year":"1982"},{"issue":"6","key":"10.1016\/0020-0255(94)00057-I_BIB5","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1137\/0219067","article-title":"An improved algorithm for approximate string matching","volume":"19","author":"Galil","year":"1990","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0020-0255(94)00057-I_BIB6","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"issue":"6","key":"10.1016\/0020-0255(94)00057-I_BIB7","doi-asserted-by":"crossref","first-page":"2261","DOI":"10.1093\/nar\/17.6.2261","article-title":"The synthesis of 2-pyrimidinone nucleosides and their incorporation into oligodeoxynucleotides","volume":"17","author":"Gildea","year":"1989","journal-title":"Nucleic Acids Res."},{"key":"10.1016\/0020-0255(94)00057-I_BIB8","series-title":"Proceedings of the 5th IEEE International Conference on Tools with Artificial Intelligence","first-page":"427","article-title":"A tool for classifying office documents","author":"Hao","year":"1993"},{"key":"10.1016\/0020-0255(94)00057-I_BIB9","series-title":"Proceedings of the 2nd International Conference on Document Analysis and Recognition","first-page":"319","article-title":"Nested segmentation: An approach for layout analysis in document classification","author":"Hao","year":"1993"},{"key":"10.1016\/0020-0255(94)00057-I_BIB10","series-title":"Artificial Intelligence and Molecular Biology","year":"1993"},{"key":"10.1016\/0020-0255(94)00057-I_BIB11","series-title":"Proceedings of the ACM-SIGMOD International Conference on the Management of Data","first-page":"312","article-title":"Randomized algorithms for optimizing large join queries","author":"Ioannidis","year":"1990"},{"key":"10.1016\/0020-0255(94)00057-I_BIB12","series-title":"Proceedings of the ACM-SIGMOD International Conference on the Management of Data","first-page":"9","article-title":"Query optimization by simulated annealing","author":"Ioannidis","year":"1987"},{"issue":"2","key":"10.1016\/0020-0255(94)00057-I_BIB13","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0020-0255(81)90052-9","article-title":"An effective algorithm for string correction using a generalized edit distance\u2014I. Description of the algorithm and its optimality","volume":"23","author":"Kashyap","year":"1981","journal-title":"Inform. Sci."},{"issue":"3","key":"10.1016\/0020-0255(94)00057-I_BIB14","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0255(81)90056-6","article-title":"An effective algorithm for string correction using a generalized edit distance\u2014II. Computational complexity of the algorithm and some applications","volume":"23","author":"Kashyap","year":"1981","journal-title":"Inform. Sci."},{"issue":"3","key":"10.1016\/0020-0255(94)00057-I_BIB15","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1109\/TSE.1983.237018","article-title":"The noisy substring matching problem","volume":"9","author":"Kashyap","year":"1983","journal-title":"IEEE Trans. Software Eng."},{"key":"10.1016\/0020-0255(94)00057-I_BIB16","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"issue":"2","key":"10.1016\/0020-0255(94)00057-I_BIB17","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","article-title":"Fast parallel and serial approximate string matching","volume":"10","author":"Landau","year":"1989","journal-title":"J. Algorithms"},{"key":"10.1016\/0020-0255(94)00057-I_BIB18","first-page":"134","article-title":"Two dimensional pattern matching in a digitized image","volume":"684","author":"Landau","year":"1993"},{"issue":"7","key":"10.1016\/0020-0255(94)00057-I_BIB19","doi-asserted-by":"crossref","first-page":"1056","DOI":"10.1109\/5.30755","article-title":"Computational approaches to discovering semantics in molecular biology","volume":"77","author":"Lipton","year":"1989","journal-title":"Proc. IEEE"},{"issue":"2","key":"10.1016\/0020-0255(94)00057-I_BIB20","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1109\/TPAMI.1984.4767511","article-title":"A tree-matching algorithm based on node splitting and merging","volume":"6","author":"Lu","year":"1984","journal-title":"IEEE Trans. Pattern Anal. Machine Intell."},{"key":"10.1016\/0020-0255(94)00057-I_BIB21","series-title":"Algorithmic Graph Theory","author":"McHugh","year":"1990"},{"key":"10.1016\/0020-0255(94)00057-I_BIB22","article-title":"A pattern matching system for biosequences","author":"Mehldau","year":"1991"},{"key":"10.1016\/0020-0255(94)00057-I_BIB23","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0022-2836(90)90312-A","article-title":"Use of techniques derived from graph theory to compare secondary structure motifs in proteins","volume":"212","author":"Mitchell","year":"1989","journal-title":"J. Molecular Biol."},{"issue":"1","key":"10.1016\/0020-0255(94)00057-I_BIB24","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF02458834","article-title":"Approximate matching of regular expressions","volume":"51","author":"Myers","year":"1989","journal-title":"Bull. Math. Biol."},{"key":"10.1016\/0020-0255(94)00057-I_BIB25","series-title":"Proceedings of the 23rd Design Automation Conference","first-page":"293","article-title":"Simulated annealing and combinatorial optimization","author":"Nahar","year":"1986"},{"key":"10.1016\/0020-0255(94)00057-I_BIB26","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connection networks and some generalizations","volume":"36","author":"Prim","year":"1957","journal-title":"Bell. Syst. Tech. J."},{"key":"10.1016\/0020-0255(94)00057-I_BIB27","series-title":"Proceedings of the 1985 IEEE Conference on VLSI","first-page":"393","article-title":"Probabilistic hill climbing algorithms: Properties and applications","author":"Romeo","year":"1985"},{"key":"10.1016\/0020-0255(94)00057-I_BIB28","series-title":"Proceedings of the 1984 IEEE International Conference on Computer Design","first-page":"652","article-title":"Research on simulated annealing at Berkeley","author":"Romeo","year":"1984"},{"key":"10.1016\/0020-0255(94)00057-I_BIB29","series-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","year":"1983"},{"key":"10.1016\/0020-0255(94)00057-I_BIB30","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","article-title":"The theory and computation of evolutionary distances","volume":"1","author":"Sellers","year":"1980","journal-title":"J. Algorithms"},{"issue":"4","key":"10.1016\/0020-0255(94)00057-I_BIB31","first-page":"309","article-title":"Comparing multiple RNA secondary structures using tree comparisons","volume":"6","author":"Shapiro","year":"1990","journal-title":"Comput. Appl. Biosci."},{"key":"10.1016\/0020-0255(94)00057-I_BIB32","series-title":"Proceedings of the 4th IEEE International Conference on Tools with Artificial Intelligence","first-page":"352","article-title":"Pattern matching in unordered trees","author":"Shasha","year":"1992"},{"issue":"4","key":"10.1016\/0020-0255(94)00057-I_BIB33","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1109\/21.286387","article-title":"Exact and approximate algorithms for unordered tree matching","volume":"24","author":"Shasha","year":"1994","journal-title":"IEEE Trans. Syst. Man Cybernetics"},{"issue":"4","key":"10.1016\/0020-0255(94)00057-I_BIB34","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1016\/0196-6774(90)90011-3","article-title":"Fast algorithms for the unit cost editing distance between trees","volume":"11","author":"Shasha","year":"1990","journal-title":"J. Algorithms"},{"key":"10.1016\/0020-0255(94)00057-I_BIB35","series-title":"Artificial Intelligence and Molecular Biology","first-page":"121","article-title":"Neural networks, adaptive optimization and RNA secondary structure prediction","author":"Steeg","year":"1993"},{"issue":"3","key":"10.1016\/0020-0255(94)00057-I_BIB36","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/322139.322143","article-title":"The tree-to-tree correction problem","volume":"26","author":"Tai","year":"1979","journal-title":"J. ACM"},{"key":"10.1016\/0020-0255(94)00057-I_BIB37","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","article-title":"Data Structures and Network Algorithms","author":"Tarjan","year":"1983"},{"key":"10.1016\/0020-0255(94)00057-I_BIB38","series-title":"Computational Chemical Graph Theory","author":"Trinajstic","year":"1991"},{"key":"10.1016\/0020-0255(94)00057-I_BIB39","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","article-title":"Finding approximate patterns in strings","volume":"6","author":"Ukkonen","year":"1985","journal-title":"J. Algorithms"},{"issue":"1","key":"10.1016\/0020-0255(94)00057-I_BIB40","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/321921.321925","article-title":"An algorithm for subgraph isomorphism","volume":"23","author":"Ullmann","year":"1976","journal-title":"J. ACM"},{"issue":"1","key":"10.1016\/0020-0255(94)00057-I_BIB41","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","article-title":"The string-to-string correction problem","volume":"21","author":"Wagner","year":"1974","journal-title":"J. ACM"},{"key":"10.1016\/0020-0255(94)00057-I_BIB42","series-title":"Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data","first-page":"115","article-title":"Combinatorial pattern discovery for scientific data: Some preliminary results","author":"Wang","year":"1994"},{"key":"10.1016\/0020-0255(94)00057-I_BIB43","article-title":"Reference manual for ATBE: A tool for approximate tree matching","author":"Wang","year":"1991"},{"issue":"14","key":"10.1016\/0020-0255(94)00057-I_BIB44","doi-asserted-by":"crossref","first-page":"2769","DOI":"10.1093\/nar\/22.14.2769","article-title":"Discovering active motifs in sets of related protein sequences and using them for classification","volume":"22","author":"Wang","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"10.1016\/0020-0255(94)00057-I_BIB45","series-title":"Proceedings of the 3rd IEEE International Conference on Tools for Artificial Intelligence","first-page":"436","article-title":"A tool for tree pattern matching","author":"Wang","year":"1991"},{"issue":"4","key":"10.1016\/0020-0255(94)00057-I_BIB46","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1109\/69.298173","article-title":"A system for approximate tree matching","volume":"6","author":"Wang","year":"1994","journal-title":"IEEE Trans. Knowledge and Data Eng."},{"key":"10.1016\/0020-0255(94)00057-I_BIB47","first-page":"254","article-title":"A new editing based distance between unordered labeled trees","volume":"684","author":"Zhang","year":"1993"},{"issue":"6","key":"10.1016\/0020-0255(94)00057-I_BIB48","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1137\/0218082","article-title":"Simple fast algorithms for the editing distance between trees and related problems","volume":"18","author":"Zhang","year":"1989","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/0020-0255(94)00057-I_BIB49","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1006\/jagm.1994.1003","article-title":"Approximate tree matching in the presence of variable length don't cares","volume":"16","author":"Zhang","year":"1994","journal-title":"J. Algorithms"},{"key":"10.1016\/0020-0255(94)00057-I_BIB50","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(92)90136-J","article-title":"On the editing distance between unordered labeled trees","volume":"42","author":"Zhang","year":"1992","journal-title":"Inform. Process. Lett."}],"container-title":["Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:002002559400057I?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:002002559400057I?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,14]],"date-time":"2019-04-14T13:50:11Z","timestamp":1555249811000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/002002559400057I"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,1]]},"references-count":50,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1995,1]]}},"alternative-id":["002002559400057I"],"URL":"https:\/\/doi.org\/10.1016\/0020-0255(94)00057-i","relation":{},"ISSN":["0020-0255"],"issn-type":[{"value":"0020-0255","type":"print"}],"subject":[],"published":{"date-parts":[[1995,1]]}}}