On the complexity of computing the temporal hybridization number for two phylogenies

DOI10.1016/j.dam.2012.11.022zbMath1318.92038MaRDI QIDQ1949091

Charles Semple, Simone Linz, Peter J. Humphries

Publication date: 25 April 2013

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.11.022

zbMATH Keywords

phylogenetic tree; phylogenetic network; temporal network; APX-hard; agreement forest

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

92D15: Problems related to evolution

Related Items

Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies, On the existence of a cherry-picking sequence, 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, New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees, Orchard networks are trees with additional horizontal arcs, The rigid hybrid number for two phylogenetic trees

Uses Software

• HybridNET

Cites Work

• Unnamed Item
• Unnamed Item
• Constructing the simplest possible phylogenetic network from triplets
• Analyzing and reconstructing reticulation networks under timing constraints
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Optimization, approximation, and complexity classes
• When two trees go to war
• Bounding the number of hybridisation events for a consistent evolutionary history
• Fundamentals of Computation Theory