Computing maximum agreement forests without cluster partitioning is folly

DOI10.4230/LIPICS.ESA.2017.56MaRDI QIDQ5111745zbMATH OpenOpenAlexFDO

Authors Zhijiang Li, Norbert Zeh

Publication date 27 May 2020

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

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)

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

Cites work

• A cluster reduction for computing the subtree distance between phylogenies
• A quadratic kernel for computing the hybridization number of multiple trees
• Approximation algorithms for nonbinary agreement forests
• Bounding the number of hybridisation events for a consistent evolutionary history
• Computing maximum agreement forests without cluster partitioning is folly
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
• Fixed-parameter algorithms for maximum agreement forests
• Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
• Improved approximation algorithm for maximum agreement forest of two trees
• On the computational complexity of the rooted subtree prune and regraft distance
• On the fixed parameter tractability of agreement-based phylogenetic distances

Cited in

(3)

• A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
• Computing maximum agreement forests without cluster partitioning is folly
• Reflections on kernelizing and computing unrooted agreement forests

Describes a project that uses

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)