File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Cavity matchings, label compressions, and unrooted evolutionary trees

TitleCavity matchings, label compressions, and unrooted evolutionary trees
Authors
Kao, MYLam, TWSung, WKTing, HF
KeywordsAll-cavity maximum weight matchings
Computational biology
Evolutionary trees
Label compressions
Mixed trees
Unrooted trees
Issue Date2000
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php
Citation
Siam Journal On Computing, 2000, v. 30 n. 2, p. 602-624 How to Cite?
DOI: http://dx.doi.org/10.1137/S0097539797332275
AbstractWe present an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n1.5 log n) time for trees with unbounded degrees, matching the best known time complexity for the rooted case. Our algorithm allows the input trees to be mixed trees, i.e., trees that may contain directed and undirected edges at the same time. Our algorithm adopts a recursive strategy exploiting a technique called label compression. The backbone of this technique is an algorithm that computes the maximum weight matchings over many subgraphs of a bipartite graph as fast as it takes to compute a single matching. © 2000 Society for Industrial and Applied Mathematics.
Persistent Identifierhttp://hdl.handle.net/10722/43657
ISSN
0097-5397
2023 Impact Factor: 1.2
2023 SCImago Journal Rankings: 2.143
ISI Accession Number ID
WOS:000088166000013
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorKao, MYen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSung, WKen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2007-03-23T04:51:23Z-
dc.date.available2007-03-23T04:51:23Z-
dc.date.issued2000en_HK
dc.identifier.citationSiam Journal On Computing, 2000, v. 30 n. 2, p. 602-624en_HK
dc.identifier.issn0097-5397en_HK
dc.identifier.urihttp://hdl.handle.net/10722/43657-
dc.description.abstractWe present an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n1.5 log n) time for trees with unbounded degrees, matching the best known time complexity for the rooted case. Our algorithm allows the input trees to be mixed trees, i.e., trees that may contain directed and undirected edges at the same time. Our algorithm adopts a recursive strategy exploiting a technique called label compression. The backbone of this technique is an algorithm that computes the maximum weight matchings over many subgraphs of a bipartite graph as fast as it takes to compute a single matching. © 2000 Society for Industrial and Applied Mathematics.en_HK
dc.format.extent285079 bytes-
dc.format.extent25600 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php-
dc.relation.ispartofSIAM Journal on Computingen_HK
dc.rights© 2000 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Computing in volume 30, issue 2, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectAll-cavity maximum weight matchingsen_HK
dc.subjectComputational biologyen_HK
dc.subjectEvolutionary treesen_HK
dc.subjectLabel compressionsen_HK
dc.subjectMixed treesen_HK
dc.subjectUnrooted treesen_HK
dc.titleCavity matchings, label compressions, and unrooted evolutionary treesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0097-5397&volume=30&issue=2&spage=602&epage=624&date=2000&atitle=Cavity+Matchings,+Label+Compressions,+and+Unrooted+Evolutionary+Treesen_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.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1137/S0097539797332275en_HK
dc.identifier.scopuseid_2-s2.0-0343337500en_HK
dc.identifier.hkuros57733-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0343337500&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume30en_HK
dc.identifier.issue2en_HK
dc.identifier.spage602en_HK
dc.identifier.epage624en_HK
dc.identifier.isiWOS:000088166000013-
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.issnl0097-5397-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats