Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees

DOI10.1016/j.tcs.2014.10.031zbMath1303.68154OpenAlexW2052824789MaRDI QIDQ476897

Sing-Hoi Sze, Jia-Hao Fan, Jian'er Chen

Publication date: 2 December 2014

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

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

zbMATH Keywords

approximation algorithmphylogenetic treefixed-parameter tractabilitymaximum agreement forest

Mathematics Subject Classification ID

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

Related Items (13)

Reduction rules for the maximum parsimony distance on phylogenetic trees ⋮ A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees ⋮ The agreement distance of unrooted phylogenetic networks ⋮ Convex Characters, Algorithms, and Matchings ⋮ Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics ⋮ New reduction rules for the tree bisection and reconnection distance ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ On the subnet prune and regraft distance ⋮ On unrooted and root-uncertain variants of several well-known phylogenetic network problems ⋮ Approximating maximum agreement forest on multiple binary trees ⋮ A note on convex characters, Fibonacci numbers and exponential-time algorithms ⋮ Reflections on kernelizing and computing unrooted agreement forests ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees

Uses Software

• rSPR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• On the linear-cost subtree-transfer distance between 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
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• Subtree transfer operations and their induced metrics on evolutionary trees
• On the complexity of comparing evolutionary trees

This page was built for publication: Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees