Kernelizations for the hybridization number problem on multiple nonbinary trees

DOI10.1016/J.JCSS.2016.03.006zbMATH Open1342.68170OpenAlexW1533847227MaRDI QIDQ295644FDOQ295644

Authors: Leo Van Iersel, Steven Kelk, Celine Scornavacca 

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

Recommendations

• Kernelizations for the hybridization number problem on multiple nonbinary trees
• A quadratic kernel for computing the hybridization number of multiple trees
• Hybridization number on three rooted binary trees is EPT
• A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
• New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees

zbMATH Keywords

phylogenetic treefixed-parameter tractabilityphylogenetic networkkernelizationhybridization number

Mathematics Subject Classification ID

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

Cites Work

• Fixed-parameter algorithms for maximum agreement forests
• Title not available (Why is that?)
• On problems without polynomial kernels
• Approximation algorithms for nonbinary agreement forests
• Bounding the number of hybridisation events for a consistent evolutionary history
• Title not available (Why is that?)
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Counting phylogenetic networks
• A quadratic kernel for computing the hybridization number of multiple trees
• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
• Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
• Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network
• Reconstructing evolution of sequences subject to recombination using parsimony

Cited In (16)

• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• Not all phylogenetic networks are leaf-reconstructible
• Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies
• Deciding the existence of a cherry-picking sequence is hard on two trees
• Embedding phylogenetic trees in networks of low treewidth
• Treewidth distance on phylogenetic trees
• Hybridization number on three rooted binary trees is EPT
• A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary 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
• Treewidth of display graphs: bounds, brambles and applications
• A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• Reflections on kernelizing and computing unrooted agreement forests
• A quadratic kernel for computing the hybridization number of multiple trees
• Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks

This page was built for publication: Kernelizations for the hybridization number problem on multiple nonbinary trees

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