Hybridization Number on Three Rooted Binary Trees is EPT

DOI10.1137/15M1036579zbMath1345.92101arXiv1402.2136OpenAlexW2963805123MaRDI QIDQ2818206

Steven Kelk, Nela Lekić, Leo van Iersel, Norbert Zeh, Chris Whidden

Publication date: 6 September 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

fixed parameter tractabilityhybridization numberreticulate evolutionrooted phylogenetic treeagreement forestrooted phylogenetic network

Mathematics Subject Classification ID

Problems related to evolution (92D15) Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Combining Networks Using Cherry Picking Sequences ⋮ Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies ⋮ When is a phylogenetic network simply an amalgamation of two trees? ⋮ 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 ⋮ 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
• Computing the minimum number of hybridization events for a consistent evolutionary history
• A supertree method for rooted trees
• A framework for representing reticulate evolution
• Bounding the number of hybridisation events for a consistent evolutionary history
• A quadratic kernel for computing the hybridization number of multiple trees
• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Kernelizations for the Hybridization Number Problem on Multiple Nonbinary Trees
• 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

This page was built for publication: Hybridization Number on Three Rooted Binary Trees is EPT