File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: An even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings

TitleAn even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings
Authors
Issue Date2001
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor
Citation
Journal Of Algorithms, 2001, v. 40 n. 2, p. 212-233 How to Cite?
AbstractA widely used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure has only been concerned with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled with the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves). This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner. In addition to this generality, this algorithm is faster than the previous algorithms. Another contribution of this paper is on maximum weight bipartite matchings. We show how to speed up the best known matching algorithms when the input graphs are node-unbalanced or weight-unbalanced. Based on these enhancements, we obtain an efficient algorithm for a new matching problem called the hierarchical bipartite matching problem, which is at the core of our maximum agreement subtree algorithm. © 2001 Academic Press.
Persistent Identifierhttp://hdl.handle.net/10722/89022
ISSN
2011 Impact Factor: 0.5
2012 SCImago Journal Rankings: 0.469
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorKao, MYen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSung, WKen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-06T09:51:25Z-
dc.date.available2010-09-06T09:51:25Z-
dc.date.issued2001en_HK
dc.identifier.citationJournal Of Algorithms, 2001, v. 40 n. 2, p. 212-233en_HK
dc.identifier.issn0196-6774en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89022-
dc.description.abstractA widely used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure has only been concerned with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled with the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves). This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner. In addition to this generality, this algorithm is faster than the previous algorithms. Another contribution of this paper is on maximum weight bipartite matchings. We show how to speed up the best known matching algorithms when the input graphs are node-unbalanced or weight-unbalanced. Based on these enhancements, we obtain an efficient algorithm for a new matching problem called the hierarchical bipartite matching problem, which is at the core of our maximum agreement subtree algorithm. © 2001 Academic Press.en_HK
dc.languageengen_HK
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgoren_HK
dc.relation.ispartofJournal of Algorithmsen_HK
dc.titleAn even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchingsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0196-6774&volume=40&issue=2&spage=212&epage=233&date=2001&atitle=An+even+faster+and+more+unifying+algorithm+for+comparing+trees+via+unbalanced+bipartite+matchingsen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1006/jagm.2001.1163en_HK
dc.identifier.scopuseid_2-s2.0-0347752674en_HK
dc.identifier.hkuros81818en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0347752674&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume40en_HK
dc.identifier.issue2en_HK
dc.identifier.spage212en_HK
dc.identifier.epage233en_HK
dc.identifier.isiWOS:000170169700004-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridKao, MY=7202198147en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridSung, WK=13310059700en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.citeulike524889-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats