Who is Who in Phylogenetic Networks

Publication no #404   Type :   Html | Bib | Both

Created: 2007-11-17 01:16:40     Modified: 2014-08-19 20:24:44

404 Magnus Bordewich and Charles Semple. On the computational complexity of the rooted subtree prune and regraft distance. In ACOM, Vol. 8:409-423, 2005. Keywords: agreement forest, from rooted trees, NP complete, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS04.pdf.         Toggle abstract "The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic 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." @Article{BordewichSemple2005,       AUTHOR = {Bordewich, Magnus and Semple, Charles},       TITLE = {On the computational complexity of the rooted subtree prune and regraft distance},       YEAR = {2005},       JOURNAL = {ACOM},       VOLUME = {8},       PAGES = {409-423},       URL = {http://dx.doi.org/10.1007/s00026-004-0229-z},       NOTE = {http://www.math.canterbury.ac.nz/~c.semple/papers/BS04.pdf},       ANNOTE = {BIBUPDATE : 20070919},       KEYWORDS = {agreement forest, from rooted trees, NP complete, SPR distance} }