A duality based 2-approximation algorithm for maximum agreement forest

We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the rooted Subtree Prune-and-Regraft (rSPR) distance between two phylogenetic trees. Our...

Descripción completa

Detalles Bibliográficos
Autores principales: Olver, Neil, Schalekamp, Frans, van der Ster, Suzanne, Stougie, Leen, van Zuylen, Anke
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer Berlin Heidelberg 2022
Materias:
Full Length Paper
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9945189/
https://www.ncbi.nlm.nih.gov/pubmed/36845754
http://dx.doi.org/10.1007/s10107-022-01790-y

Internet

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9945189/
https://www.ncbi.nlm.nih.gov/pubmed/36845754
http://dx.doi.org/10.1007/s10107-022-01790-y

Ejemplares similares