Fixed-Parameter Algorithms for Maximum Agreement Forests

DOI10.1137/110845045zbMath1311.68079arXiv1108.2664OpenAlexW2042774332MaRDI QIDQ2862198

Chris Whidden, Robert G. Beiko, Norbert Zeh

Publication date: 14 November 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1108.2664

zbMATH Keywords

fixed-parameter tractabilityhybridizationphylogeneticslateral gene transferagreement forestsubtree prune-and-regraft distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Problems related to evolution (92D15) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Related Items (34)

Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees ⋮ Combining Networks Using Cherry Picking Sequences ⋮ Kernelizations for the hybridization number problem on multiple nonbinary trees ⋮ Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees ⋮ A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees ⋮ Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph ⋮ Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies ⋮ Reconciliation of a gene network and species tree ⋮ The agreement distance of unrooted phylogenetic networks ⋮ Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance ⋮ Convex Characters, Algorithms, and Matchings ⋮ Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics ⋮ A duality based 2-approximation algorithm for maximum agreement forest ⋮ Ranked subtree prune and regraft ⋮ New reduction rules for the tree bisection and reconnection distance ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ A quadratic kernel for computing the hybridization number of multiple trees ⋮ Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable ⋮ Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees ⋮ Scanning Phylogenetic Networks Is NP-hard ⋮ Deciding the existence of a cherry-picking sequence is hard on two trees ⋮ On the fixed parameter tractability of agreement-based phylogenetic distances ⋮ On unrooted and root-uncertain variants of several well-known phylogenetic network problems ⋮ Approximating maximum agreement forest on multiple binary trees ⋮ Algorithms for parameterized maximum agreement forest problem on multiple trees ⋮ Hybridization Number on Three Rooted Binary Trees is EPT ⋮ rSPR ⋮ Better Practical Algorithms for rSPR Distance and Hybridization Number ⋮ Reflections on kernelizing and computing unrooted agreement forests ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees ⋮ Computing Maximum Agreement Forests without Cluster Partitioning is Folly ⋮ Not all phylogenetic networks are leaf-reconstructible ⋮ On the maximum parsimony distance between phylogenetic trees ⋮ A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees

This page was built for publication: Fixed-Parameter Algorithms for Maximum Agreement Forests