A quadratic kernel for computing the hybridization number of multiple trees

DOI10.1016/j.ipl.2013.02.010zbMath1287.68060arXiv1203.4067OpenAlexW2163883053MaRDI QIDQ2450929

Simone Linz, Leo van Iersel

Publication date: 26 May 2014

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

generatorcomputational complexitykernelfixed-parameter tractabilityhybridizationphylogenetic network

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) Systems biology, networks (92C42)

Related Items (11)

Combining Networks Using Cherry Picking Sequences ⋮ Kernelizations for the hybridization number problem on multiple nonbinary trees ⋮ Treewidth distance on phylogenetic trees ⋮ A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees ⋮ Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance ⋮ On unrooted and root-uncertain variants of several well-known phylogenetic network problems ⋮ Hybridization Number on Three Rooted Binary Trees is EPT ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees ⋮ Heading in the right direction? Using head moves to traverse phylogenetic network space ⋮ Computing Maximum Agreement Forests without Cluster Partitioning is Folly ⋮ A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees

Cites Work

• Computing the minimum number of hybridization events for a consistent evolutionary history
• Seeing the trees and their branches in the network is hard
• On the computational complexity of the rooted subtree prune and regraft distance
• When two trees go to war
• Bounding the number of hybridisation events for a consistent evolutionary history
• 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

This page was built for publication: A quadratic kernel for computing the hybridization number of multiple trees