On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance

Simple item page
dc.contributor.authorBordewich, M.
dc.contributor.authorSemple, C.
dc.date.accessioned2008-11-03T20:02:13Z
dc.date.available2008-11-03T20:02:13Z
dc.date.issued2004en
dc.description.abstractThe graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticu- lation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phy- logenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees.en
dc.identifier.citationBordewich, M., Semple, C. (2004) On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance. Annals of Combinatorics, 8(4), pp. 409-423.en
dc.identifier.doihttps://doi.org/10.1007/s00026-004-0229-z
dc.identifier.issn0218-0006 (print)
dc.identifier.issn0219-3094 (online)
dc.identifier.urihttp://hdl.handle.net/10092/1755
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.subject.marsdenFields of Research::270000 Biological Sciences::270700 Ecology and Evolution::270799 Ecology and evolution not elsewhere classifieden
dc.titleOn the Computational Complexity of the Rooted Subtree Prune and Regraft Distanceen
dc.typeJournal Article
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
12592691_BS04.pdf
Size:
179.94 KB
Format:
Adobe Portable Document Format
Download
Collections
Engineering: Journal Articles