Kernelizations for the hybridization number problem on multiple nonbinary trees

DOI10.1016/j.jcss.2016.03.006zbMath1342.68170OpenAlexW1533847227MaRDI QIDQ295644

Steven Kelk, Celine Scornavacca, Leo van Iersel

Publication date: 13 June 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2016.03.006

zbMATH Keywords

phylogenetic treefixed-parameter tractabilityphylogenetic networkkernelizationhybridization number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Treewidth distance on phylogenetic trees, New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees, Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance, Deciding the existence of a cherry-picking sequence is hard on two trees, On unrooted and root-uncertain variants of several well-known phylogenetic network problems, Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks, Treewidth of display graphs: bounds, brambles and applications, Reflections on kernelizing and computing unrooted agreement forests, A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees, Not all phylogenetic networks are leaf-reconstructible, A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees

Cites Work

• Unnamed Item
• Unnamed Item
• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
• Reconstructing evolution of sequences subject to recombination using parsimony
• Computing the minimum number of hybridization events for a consistent evolutionary history
• On problems without polynomial kernels
• Counting phylogenetic networks
• 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
• Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
• Approximation Algorithms for Nonbinary Agreement Forests
• Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network