P. Berman, M. Karpinski, and A. D. Scott, Approximation hardness and satisfiability of bounded occurrence instances of SAT, Electronic Colloquium on Computational Complexity (ECCC), vol.10, issue.022, 2003.

M. A. Biscotti, E. Olmo, and J. S. Heslop-harrison, Repetitive DNA in eukaryotic genomes, Chromosome Res, vol.23, issue.3, pp.415-420, 2015.

D. L. Cameron, J. Schroder, J. S. Penington, H. Do, R. Molania et al., GRIDSS: sensitive and specific genomic rearrangement detection using positional de Bruijn graph assembly, Genome Res, vol.27, issue.12, pp.2050-2060, 2017.

A. Chateau and R. Giroudeau, A complexity and approximation framework for the maximization scaffolding problem, Theoretical Computer Science, vol.595, pp.92-106, 2015.
URL : https://hal.archives-ouvertes.fr/lirmm-01219622

R. Chikhi and G. Rizk, Space-efficient and exact de Bruijn graph representation based on a Bloom filter, WABI, pp.236-248, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00868805

R. Ekblom and J. B. Wolf, A field guide to whole-genome sequencing, assembly and annotation, Evol Appl, vol.7, issue.9, pp.1026-1042, 2014.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

J. Håstad, Some optimal inapproximability results, J. ACM, vol.48, issue.4, pp.798-859, 2001.

P. Koch, M. Platzer, and B. R. Downie, RepARK-de novo creation of repeat libraries from whole-genome NGS reads, Nucleic Acids Res, vol.42, issue.9, p.80, 2014.

H. Li and R. Durbin, Fast and accurate long-read alignment with BurrowsWheeler transform, Bioinformatics, vol.26, issue.5, pp.589-595, 2010.

H. Li, B. Handsaker, A. Wysoker, T. Fennell, J. Ruan et al., The sequence alignment/map format and samtools, Bioinformatics, vol.25, issue.16, pp.2078-2079, 2009.

D. Lichtenstein, Planar formulae and their uses, SIAM Journal on Computing, vol.11, issue.2, pp.329-343, 1982.

D. Lokshtanov, D. Marx, and S. Saurabh, Lower bounds based on the Exponential Time Hypothesis, Bulletin of the EATCS, vol.105, pp.41-72, 2011.

I. Mandric, J. Lindsay, I. I. M?ndoiu, and A. Zelikovsky, Scaffolding algorithms, Computational Methods for Next Generation Sequencing Data Analysis, pp.107-132, 2016.

A. Morgulis, G. Coulouris, Y. Raytselis, T. L. Madden, R. Agarwala et al., Database indexing for production megablast searches, Bioinformatics, vol.24, issue.16, pp.1757-1764, 2008.

C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, Journal of Computer and System Sciences, vol.43, issue.3, pp.425-440, 1991.

M. A. Quail, M. Smith, P. Coupland, T. D. Otto, S. R. Harris et al., A tale of three next generation sequencing platforms: comparison of ion torrent, pacific biosciences and illumina miseq sequencers, BMC Genomics, vol.13, issue.1, p.341, 2012.

H. Tang, Genome assembly, rearrangement, and repeats, Chemical Reviews, vol.107, issue.8, pp.3391-3406, 2007.

L. Trevisan, Non-approximability results for optimization problems on bounded degree instances, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, pp.453-461, 2001.

M. Weller, A. Chateau, and R. Giroudeau, Exact approaches for scaffolding, BMC Bioinformatics, vol.16, p.2, 2015.
URL : https://hal.archives-ouvertes.fr/lirmm-01219627

M. Weller, A. Chateau, and R. Giroudeau, On the linearization of scaffolds sharing repeated contigs, Proc. 11th COCOA'17, pp.509-517, 2017.
URL : https://hal.archives-ouvertes.fr/lirmm-01672893

M. Weller, A. Chateau, C. Dallard, and R. Giroudeau, Scaffolding problems revisited: Complexity, approximation and fixed parameter tractable algorithms, and some special cases, Algorithmica, vol.80, issue.6, pp.1771-1803, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01833303

M. Weller, A. Chateau, R. Giroudeau, and M. Poss, Scaffolding with repeated contigs using flow formulations, 2018.