18 citations · 79 across the 28 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
math.CO2011
Cycle killer... qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set
Steven Kelk, Leo van Iersel, Nela Lekic +3
We show that the problem of computing the hybridization number of two rooted binary phylogenetic trees on the same set of taxa X has a constant factor polynomial-time approximation…
q-bio.PE2011
The Complexity of Finding Multiple Solutions to Betweenness and Quartet Compatibility
Maria Luisa Bonet, Simone Linz, Katherine St. John
We show that two important problems that have applications in computational biology are ASP-complete, which implies that, given a solution to a problem, it is NP-complete to decide…