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

DOI10.1016/j.dam.2012.11.022zbMath1318.92038OpenAlexW1988903798MaRDI 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 treephylogenetic networktemporal networkAPX-hardagreement forest

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15)

Related Items (7)

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 ⋮ 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

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

This page was built for publication: On the complexity of computing the temporal hybridization number for two phylogenies