A 3-approximation algorithm for the subtree between phylogenies
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.
SubjectsField of Research::01 - Mathematical Sciences::0102 - Applied Mathematics::010202 - Biological Mathematics
- Engineering: Reports