Computing maximum agreement forests without cluster partitioning is folly

DOI10.4230/LIPICS.ESA.2017.56zbMATH Open1442.68287OpenAlexW2758315610MaRDI QIDQ5111745FDOQ5111745

Authors: Zhijiang Li, Norbert Zeh 

Publication date: 27 May 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.ESA.2017.56

Recommendations

• Parameterized algorithms for maximum agreement forest on multiple trees
• Fixed-parameter algorithms for maximum agreement forests
• A faster FPT algorithm for the maximum agreement forest problem
• Algorithms for parameterized maximum agreement forest problem on multiple trees
• Approximation algorithms for nonbinary agreement forests

zbMATH Keywords

hybridizationfixed-parameter tractabilityagreement forestssubtree prune-and-regraft

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) Analysis of algorithms (68W40) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Fixed-parameter algorithms for maximum agreement forests
• On the computational complexity of the rooted subtree prune and regraft distance
• Approximation Algorithms for Nonbinary Agreement Forests
• A cluster reduction for computing the subtree distance between phylogenies
• Bounding the number of hybridisation events for a consistent evolutionary history
• Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
• Computing the minimum number of hybridization events for a consistent evolutionary history
• A quadratic kernel for computing the hybridization number of multiple trees
• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
• On the fixed parameter tractability of agreement-based phylogenetic distances
• Improved Approximation Algorithm for Maximum Agreement Forest of Two Trees
• Computing Maximum Agreement Forests without Cluster Partitioning is Folly

Cited In (3)

• Computing Maximum Agreement Forests without Cluster Partitioning is Folly
• A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
• Reflections on kernelizing and computing unrooted agreement forests

Uses Software

• SPRSupertrees

This page was built for publication: Computing maximum agreement forests without cluster partitioning is folly

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