Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

A 3-approximation algorithm for the subtree distance between phylogenies.

Bordewich, M. and McCartin, C. and Semple, C. (2008) 'A 3-approximation algorithm for the subtree distance between phylogenies.', Journal of discrete algorithms., 6 (3). pp. 458-471.

Abstract

In 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.

Item Type:Article
Keywords:Rooted subtree prune and regraft, Agreement forest.
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1016/j.jda.2007.10.002
Date accepted:No date available
Date deposited:No date available
Date of first online publication:September 2008
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar