Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


Durham Research Online
You are in:

On the computational complexity of the rooted subtree prune and regraft distance.

Bordewich, M. and Semple, C. (2005) 'On the computational complexity of the rooted subtree prune and regraft distance.', Annals of combinatorics., 8 (4). pp. 409-423.

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 xed parameter tractable when parameterised by the distance between the two trees.

Item Type:Article
Keywords:Rooted phylogenetic tree, Rooted subtree prune, Regraft.
Full text:PDF - Accepted Version (188Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/s00026-004-0229-z
Publisher statement:The original publication is available at www.springerlink.com
Record Created:13 Oct 2008
Last Modified:15 Jun 2011 16:51

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library