The Most Parsimonious Reconciliation Problem in the Presence of Incomplete Lineage Sorting and Hybridization Is NP-Hard.
Matthew LeMayYi-Chieh WuRan Libeskind-HadasPublished in: WABI (2021)
Keyphrases
- np hard
- approximation algorithms
- closely related
- scheduling problem
- lower bound
- optimal solution
- linear programming
- special case
- decision problems
- branch and bound algorithm
- worst case
- np complete
- computational complexity
- data lineage
- minimum cost
- greedy heuristic
- np hardness
- real time
- remains np hard
- dna computing
- set cover
- scientific data
- missing values