File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: General techniques for comparing unrooted evolutionary trees

TitleGeneral techniques for comparing unrooted evolutionary trees
Authors
Issue Date1997
PublisherThe Association for Computing Machinery.
Citation
Conference Proceedings Of The Annual Acm Symposium On Theory Of Computing, 1997, p. 54-65 How to Cite?
AbstractThis 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 Identifierhttp://hdl.handle.net/10722/93170
ISSN

 

DC FieldValueLanguage
dc.contributor.authorKao, MingYangen_HK
dc.contributor.authorLam, TakWahen_HK
dc.contributor.authorPrzytycka, Teresa Men_HK
dc.contributor.authorSung, WingKinen_HK
dc.contributor.authorTing, HingFungen_HK
dc.date.accessioned2010-09-25T14:53:01Z-
dc.date.available2010-09-25T14:53:01Z-
dc.date.issued1997en_HK
dc.identifier.citationConference Proceedings Of The Annual Acm Symposium On Theory Of Computing, 1997, p. 54-65en_HK
dc.identifier.issn0734-9025en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93170-
dc.description.abstractThis 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.languageengen_HK
dc.publisherThe Association for Computing Machinery.en_HK
dc.relation.ispartofConference Proceedings of the Annual ACM Symposium on Theory of Computingen_HK
dc.titleGeneral techniques for comparing unrooted evolutionary treesen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, TakWah:twlam@cs.hku.hken_HK
dc.identifier.emailTing, HingFung:hfting@cs.hku.hken_HK
dc.identifier.authorityLam, TakWah=rp00135en_HK
dc.identifier.authorityTing, HingFung=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-0030642910en_HK
dc.identifier.hkuros38531en_HK
dc.identifier.spage54en_HK
dc.identifier.epage65en_HK
dc.identifier.scopusauthoridKao, MingYang=7202198147en_HK
dc.identifier.scopusauthoridLam, TakWah=7202523165en_HK
dc.identifier.scopusauthoridPrzytycka, Teresa M=6603727550en_HK
dc.identifier.scopusauthoridSung, WingKin=13310059700en_HK
dc.identifier.scopusauthoridTing, HingFung=7005654198en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats