Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees

DOI10.1016/J.TCS.2014.10.031zbMATH Open1303.68154OpenAlexW2052824789MaRDI QIDQ476897FDOQ476897

Authors: Jia-Hao Fan, Sing-Hoi Sze, Jianer 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

Recommendations

• Parameterized and approximation algorithms for the MAF problem in multifurcating trees
• A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
• Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
• Algorithms for parameterized maximum agreement forest problem on multiple trees
• Parameterized algorithms for maximum agreement forest on multiple trees

zbMATH Keywords

phylogenetic treeapproximation algorithmfixed-parameter tractabilitymaximum agreement forest

Mathematics Subject Classification ID

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

Cites Work

• Fixed-parameter algorithms for maximum agreement forests
• On the linear-cost subtree-transfer distance between phylogenetic trees
• On the computational complexity of the rooted subtree prune and regraft distance
• Subtree transfer operations and their induced metrics on evolutionary trees
• On the complexity of comparing evolutionary trees
• The maximum agreement forest problem: Approximation algorithms and computational experiments
• A 3-approximation algorithm for the subtree distance between phylogenies
• Title not available (Why is that?)
• A faster FPT algorithm for the maximum agreement forest problem
• Title not available (Why is that?)
• Approximating the maximum agreement forest on \(k\) trees
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• Title not available (Why is that?)

Cited In (16)

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

Uses Software

• rSPR

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476897)