|
|||||
|
|
A 3-approximation algorithm for the subtree distance between phylogenies |
|
| Authors: | Magnus Bordewich Catherine McCartin Charles Semple |
| Affiliation: | aDepartment of Computer Science, Durham University, Durham DH1 3LE, United Kingdom;bInstitute of Information Sciences and Technology, Massey University, Palmerston North, New Zealand;cBiomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand |
| 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. |
| Keywords: | Rooted subtree prune and regraft Agreement forest |
| 本文献已被 ScienceDirect 等数据库收录！ | |