A 3-approximation algorithm for the subtree distance between phylogenies

Simple item page
dc.contributor.authorBordewich, M.
dc.contributor.authorMcCartin, C.
dc.contributor.authorSemple, C.
dc.date.accessioned2008-11-09T23:46:36Z
dc.date.available2008-11-09T23:46:36Z
dc.date.issued2008en
dc.description.abstractIn this paper, we give a (polynomial-time) 3-approximation algorithm for the rooted subtree prune and regraft distance between two phylogenetic trees. This problem is known to be NP-complete and the best previously known approximation algorithm is a 5-approximation. We also give a faster fixed-parameter algorithm for the rooted subtree prune and regraft distance than was previously known.en
dc.identifier.citationBordewich, M., McCartin, C., Semple, C. (2008) A 3-approximation algorithm for the subtree distance between phylogenies. Journal of Discrete Algorithms, 6(3), pp. 458-471.en
dc.identifier.doihttps://doi.org/10.1016/j.jda.2007.10.002
dc.identifier.urihttp://hdl.handle.net/10092/1774
dc.language.isoen
dc.publisherUniversity of Canterbury. Mathematics and Statistics.en
dc.rights.urihttps://hdl.handle.net/10092/17651en
dc.subject.marsdenFields of Research::230000 Mathematical Sciences::239900 Other Mathematical Sciences::239901 Biological Mathematicsen
dc.titleA 3-approximation algorithm for the subtree distance between phylogeniesen
dc.typeJournal Article
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
12610733_BMS07.pdf
Size:
242.05 KB
Format:
Adobe Portable Document Format
Download
Collections
Engineering: Journal Articles