File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1006/jagm.2001.1163
- Scopus: eid_2-s2.0-0347752674
- WOS: WOS:000170169700004
- Find via
Supplementary
-
Bookmarks:
- CiteULike: 1
- Citations:
- Appears in Collections:
Article: An even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings
Title | An even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings |
---|---|
Authors | |
Issue Date | 2001 |
Publisher | Academic 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? |
Abstract | A 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 Identifier | http://hdl.handle.net/10722/89022 |
ISSN | 2011 Impact Factor: 0.500 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kao, MY | en_HK |
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Sung, WK | en_HK |
dc.contributor.author | Ting, HF | en_HK |
dc.date.accessioned | 2010-09-06T09:51:25Z | - |
dc.date.available | 2010-09-06T09:51:25Z | - |
dc.date.issued | 2001 | en_HK |
dc.identifier.citation | Journal Of Algorithms, 2001, v. 40 n. 2, p. 212-233 | en_HK |
dc.identifier.issn | 0196-6774 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89022 | - |
dc.description.abstract | A 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.language | eng | en_HK |
dc.publisher | Academic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor | en_HK |
dc.relation.ispartof | Journal of Algorithms | en_HK |
dc.title | An even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+matchings | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.email | Ting, HF:hfting@cs.hku.hk | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.identifier.authority | Ting, HF=rp00177 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1006/jagm.2001.1163 | en_HK |
dc.identifier.scopus | eid_2-s2.0-0347752674 | en_HK |
dc.identifier.hkuros | 81818 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0347752674&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 40 | en_HK |
dc.identifier.issue | 2 | en_HK |
dc.identifier.spage | 212 | en_HK |
dc.identifier.epage | 233 | en_HK |
dc.identifier.isi | WOS:000170169700004 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Kao, MY=7202198147 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Sung, WK=13310059700 | en_HK |
dc.identifier.scopusauthorid | Ting, HF=7005654198 | en_HK |
dc.identifier.citeulike | 524889 | - |
dc.identifier.issnl | 0196-6774 | - |