Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds
From MaRDI portal
Publication:2037107
DOI10.1007/s00453-021-00819-6OpenAlexW3158374272MaRDI QIDQ2037107
Mathias Weller, Tom Davot, Rodolphe Giroudeau, Dorine Tabary, Annie Chateau
Publication date: 30 June 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-03218029v1/file/main_llncs.pdf
Uses Software
Cites Work
- On the hardness of approximating minimum vertex cover
- Optimization, approximation, and complexity classes
- Which problems have strongly exponential complexity?
- On the linearization of scaffolds sharing repeated contigs
- New results about the linearization of scaffolds sharing repeated contigs
- A complexity and approximation framework for the maximization scaffolding problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Unnamed Item