A 3-approximation algorithm for the subtree distance between phylogenies

DOI10.1016/j.jda.2007.10.002zbMath1171.05317OpenAlexW2042877799MaRDI QIDQ1018098

Charles Semple, Magnus Bordewich, Catherine McCartin

Publication date: 13 May 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.10.002

zbMATH Keywords

agreement forestrooted subtree prune and regraft

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15)

Related Items (11)

Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees ⋮ Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees ⋮ A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees ⋮ The agreement distance of unrooted phylogenetic networks ⋮ A duality based 2-approximation algorithm for maximum agreement forest ⋮ Walks in phylogenetic treespace ⋮ Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees ⋮ Approximating maximum agreement forest on multiple binary trees ⋮ Algorithms for parameterized maximum agreement forest problem on multiple trees ⋮ An Improved Approximation Algorithm for rSPR Distance ⋮ Faster exact computation of rSPR distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing evolution of sequences subject to recombination using parsimony
• Computing the minimum number of hybridization events for a consistent evolutionary history
• On the computational complexity of the rooted subtree prune and regraft distance
• A faster FPT algorithm for the maximum agreement forest problem
• On the complexity of comparing evolutionary trees

This page was built for publication: A 3-approximation algorithm for the subtree distance between phylogenies