File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: General techniques for comparing unrooted evolutionary trees
Title | General techniques for comparing unrooted evolutionary trees |
---|---|
Authors | |
Issue Date | 1997 |
Publisher | The Association for Computing Machinery. |
Citation | Conference Proceedings Of The Annual Acm Symposium On Theory Of Computing, 1997, p. 54-65 How to Cite? |
Abstract | This paper presents two sets of techniques for comparing unrooted evolutionary trees, namely, label compression and four-way dynamic programming. The technique of four-way dynamic programming transforms existing algorithms for computing rooted maximum agreement subtrees into new ones for unrooted trees. Let n be the size of the two input trees. This technique leads to an O(n log n)-time algorithm for unrooted trees whose degrees are bounded by a constant, matching the best known complexity for the rooted binary case. The technique of label compression is not based on dynamic programming. With this technique, we obtain an O(n1.5 log n)-time algorithm for unrooted trees with arbitrary degrees, also matching the best algorithm for the rooted unbounded degree case. |
Persistent Identifier | http://hdl.handle.net/10722/93170 |
ISSN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kao, MingYang | en_HK |
dc.contributor.author | Lam, TakWah | en_HK |
dc.contributor.author | Przytycka, Teresa M | en_HK |
dc.contributor.author | Sung, WingKin | en_HK |
dc.contributor.author | Ting, HingFung | en_HK |
dc.date.accessioned | 2010-09-25T14:53:01Z | - |
dc.date.available | 2010-09-25T14:53:01Z | - |
dc.date.issued | 1997 | en_HK |
dc.identifier.citation | Conference Proceedings Of The Annual Acm Symposium On Theory Of Computing, 1997, p. 54-65 | en_HK |
dc.identifier.issn | 0734-9025 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/93170 | - |
dc.description.abstract | This paper presents two sets of techniques for comparing unrooted evolutionary trees, namely, label compression and four-way dynamic programming. The technique of four-way dynamic programming transforms existing algorithms for computing rooted maximum agreement subtrees into new ones for unrooted trees. Let n be the size of the two input trees. This technique leads to an O(n log n)-time algorithm for unrooted trees whose degrees are bounded by a constant, matching the best known complexity for the rooted binary case. The technique of label compression is not based on dynamic programming. With this technique, we obtain an O(n1.5 log n)-time algorithm for unrooted trees with arbitrary degrees, also matching the best algorithm for the rooted unbounded degree case. | en_HK |
dc.language | eng | en_HK |
dc.publisher | The Association for Computing Machinery. | en_HK |
dc.relation.ispartof | Conference Proceedings of the Annual ACM Symposium on Theory of Computing | en_HK |
dc.title | General techniques for comparing unrooted evolutionary trees | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Lam, TakWah:twlam@cs.hku.hk | en_HK |
dc.identifier.email | Ting, HingFung:hfting@cs.hku.hk | en_HK |
dc.identifier.authority | Lam, TakWah=rp00135 | en_HK |
dc.identifier.authority | Ting, HingFung=rp00177 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.scopus | eid_2-s2.0-0030642910 | en_HK |
dc.identifier.hkuros | 38531 | en_HK |
dc.identifier.spage | 54 | en_HK |
dc.identifier.epage | 65 | en_HK |
dc.identifier.scopusauthorid | Kao, MingYang=7202198147 | en_HK |
dc.identifier.scopusauthorid | Lam, TakWah=7202523165 | en_HK |
dc.identifier.scopusauthorid | Przytycka, Teresa M=6603727550 | en_HK |
dc.identifier.scopusauthorid | Sung, WingKin=13310059700 | en_HK |
dc.identifier.scopusauthorid | Ting, HingFung=7005654198 | en_HK |
dc.identifier.issnl | 0734-9025 | - |