Approximating maximum agreement forest on multiple binary trees

DOI10.1007/s00453-015-0087-6zbMath1352.68288OpenAlexW2231561873MaRDI QIDQ727962

Feng Shi, Jianxin Wang, Jian'er Chen

Publication date: 21 December 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0087-6

zbMATH Keywords

approximation algorithmphylogenetic treemaximum agreement forest

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Approximation algorithms (68W25)

Related Items (11)

Dealing with several parameterized problems by random methods ⋮ Parameterized algorithms for edge biclique and related problems ⋮ Gene tree reconciliation including transfers with replacement is NP-hard and FPT ⋮ A duality based 2-approximation algorithm for maximum agreement forest ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ An improved kernel for max-bisection above tight lower bound ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ On unrooted and root-uncertain variants of several well-known phylogenetic network problems ⋮ Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition ⋮ Improved approximation algorithms for two-stage flowshops scheduling problem ⋮ New kernels for several problems on planar graphs

Uses Software

• rSPR
• SPRSupertrees

Cites Work

• Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees
• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• Algorithms for parameterized maximum agreement forest problem on multiple trees
• Approximating the maximum agreement forest on \(k\) trees
• A 3-approximation algorithm for the subtree distance between phylogenies
• The maximum agreement forest problem: Approximation algorithms and computational experiments
• Comparison of phylogenetic trees
• On the computational complexity of the rooted subtree prune and regraft distance
• A faster FPT algorithm for the maximum agreement forest problem
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Subtree transfer operations and their induced metrics on evolutionary trees
• On the complexity of comparing evolutionary trees
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating maximum agreement forest on multiple binary trees