Computing Maximum Agreement Forests without Cluster Partitioning is Folly

DOI10.4230/LIPIcs.ESA.2017.56zbMath1442.68287OpenAlexW2758315610MaRDI QIDQ5111745

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

fixed-parameter tractabilityhybridizationagreement forestssubtree prune-and-regraft

Mathematics Subject Classification ID

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

Related Items

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

Uses Software

• SPRSupertrees

Cites Work

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