{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:25:36Z","timestamp":1761611136150},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1996,3]]},"abstract":"<jats:p> We consider the problem of comparing CUAL graphs (Connected, Undirected, Acyclic graphs with nodes being Labeled). This problem is motivated by the study of information retrieval for bio-chemical and molecular databases. Suppose we define the distance between two CUAL graphs G<jats:sub>1<\/jats:sub> and G<jats:sub>2<\/jats:sub> to be the weighted number of edit operations (insert node, delete node and relabel node) to transform G<jats:sub>1<\/jats:sub> to G<jats:sub>2<\/jats:sub>. By reduction from exact cover by 3-sets, one can show that finding the distance between two CUAL graphs is NP-complete. In view of the hardness of the problem, we propose a constrained distance metric, called the degree-2 distance, by requiring that any node to be inserted (deleted) have no more than 2 neighbors. With this metric, we present an efficient algorithm to solve the problem. The algorithm runs in time O(N<jats:sub>1<\/jats:sub>N<jats:sub>2<\/jats:sub>D<jats:sup>2<\/jats:sup>) for general weighting edit operations and in time [Formula: see text] for integral weighting edit operations, where N<jats:sub>i<\/jats:sub>, i=1, 2, is the number of nodes in G<jats:sub>i<\/jats:sub>, D=min{d<jats:sub>1<\/jats:sub>, d<jats:sub>2<\/jats:sub>} and d<jats:sub>i<\/jats:sub> is the maximum degree of G<jats:sub>i<\/jats:sub>. <\/jats:p>","DOI":"10.1142\/s0129054196000051","type":"journal-article","created":{"date-parts":[[2004,9,6]],"date-time":"2004-09-06T11:50:09Z","timestamp":1094471409000},"page":"43-57","source":"Crossref","is-referenced-by-count":70,"title":["ON THE EDITING DISTANCE BETWEEN UNDIRECTED ACYCLIC GRAPHS"],"prefix":"10.1142","volume":"07","author":[{"given":"KAIZHONG","family":"ZHANG","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Western Ontario, London, Ontario, N6A 5B7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JASON T.L.","family":"WANG","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, New Jersey Institute of Technology, University Heights, Newark, New Jersey 07102, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DENNIS","family":"SHASHA","sequence":"additional","affiliation":[{"name":"Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, New York 10012, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054196000051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:43:10Z","timestamp":1565138590000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054196000051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,3]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1996,3]]}},"alternative-id":["10.1142\/S0129054196000051"],"URL":"https:\/\/doi.org\/10.1142\/s0129054196000051","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,3]]}}}