Complexity insights of the minimum duplication problem
DOI10.1016/J.TCS.2014.02.025zbMATH Open1359.68117OpenAlexW2181191890MaRDI QIDQ2440167FDOQ2440167
Authors: Guillaume Blin, Paola Bonizzoni, Riccardo Dondi, Romeo Rizzi, Florian Sikora 
Publication date: 27 March 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.02.025
Recommendations
- Complexity insights of the minimum duplication problem
- scientific article; zbMATH DE number 1303034
- Computing a smallest multi-labeled phylogenetic tree from rooted triplets
- An approximation algorithm for computing a parsimonious first speciation in the gene duplication model
- Reconciling a gene tree to a species tree under the duplication cost model
computational complexityrandomized algorithmAPX-hardnesscomparative genomicsminimum duplication problem
Genetics and epigenetics (92D10) Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational methods for problems pertaining to biology (92-08)
Cites Work
- Reconciling a gene tree to a species tree under the duplication cost model
- Some APX-completeness results for cubic graphs
- An upper bound for the chromatic number of a graph and its application to timetabling problems
- New results on optimizing rooted triplets consistency
- Reconciling Gene Trees with Apparent Polytomies
- From Gene Trees to Species Trees
- Title not available (Why is that?)
- The gene evolution model and computing its associated probabilities
- An approximation algorithm for computing a parsimonious first speciation in the gene duplication model
- Complexity insights of the minimum duplication problem
- Resolving rooted triplet inconsistency by dissolving multigraphs
Cited In (4)
- Complexity insights of the minimum duplication problem
- Correcting gene trees by leaf insertions: complexity and approximation
- Correcting gene tree by removal and modification: tractability and approximability
- An approximation algorithm for computing a parsimonious first speciation in the gene duplication model
Uses Software
This page was built for publication: Complexity insights of the minimum duplication problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2440167)
