The maximum agreement forest problem: Approximation algorithms and computational experiments

DOI10.1016/j.tcs.2006.12.011zbMath1164.68039OpenAlexW2080787406WikidataQ124796546 ScholiaQ124796546MaRDI QIDQ1022593

Marie-France Sagot, Yoshiko Wakabayashi, Estela M. Rodrigues

Publication date: 22 June 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.12.011

zbMATH Keywords

computational complexityapproximation algorithmphylogenetic treeAPX-completeevolutionary processagreement forest

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Approximation algorithms (68W25)

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 ⋮ 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 ⋮ On the maximum parsimony distance between phylogenetic trees

Cites Work

• Approximating the maximum agreement forest on \(k\) trees
• Subtree transfer operations and their induced metrics on evolutionary trees
• On the complexity of comparing evolutionary trees
• Unnamed Item
• Unnamed Item

This page was built for publication: The maximum agreement forest problem: Approximation algorithms and computational experiments