{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:39Z","timestamp":1759638399236},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319079523"},{"type":"electronic","value":"9783319079530"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07953-0_4","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T16:58:08Z","timestamp":1402419488000},"page":"47-58","source":"Crossref","is-referenced-by-count":5,"title":["Complexity and Polynomial-Time Approximation Algorithms around the Scaffolding Problem"],"prefix":"10.1007","author":[{"given":"Annie","family":"Chateau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodolphe","family":"Giroudeau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Burton, J.N., Adey, A., Patwardhan, R.P., Qiu, R., Kitzman, J.O., Shendure, J.: Chromosome-scale scaffolding of de novo genome assemblies based on chromatin interactions. Nature Biotechnology, 1119\u20131125 (November 2013)","DOI":"10.1038\/nbt.2727"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/978-3-642-45278-9_37","volume-title":"Combinatorial Algorithms","author":"C. Chauve","year":"2013","unstructured":"Chauve, C., Patterson, M., Rajaraman, A.: Hypergraph covering problems motivated by genome assembly questions. In: Lecroq, T., Mouchard, L. (eds.) IWOCA 2013. LNCS, vol.\u00a08288, pp. 428\u2013432. Springer, Heidelberg (2013)"},{"issue":"3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/j.disc.2012.10.010","volume":"313","author":"S. Chiba","year":"2013","unstructured":"Chiba, S., Fujita, S.: Covering vertices by a specified number of disjoint cycles, edges and isolated vertices. Discrete Mathematics\u00a0313(3), 269\u2013277 (2013)","journal-title":"Discrete Mathematics"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1186\/1471-2105-11-345","volume":"11","author":"A. Dayarian","year":"2010","unstructured":"Dayarian, A., Michael, T.P., Sengupta, A.M.: SOPRA: scaffolding algorithm for paired reads via statistical optimization. BMC Bioinformatics\u00a011, 345 (2010)","journal-title":"BMC Bioinformatics"},{"issue":"4","key":"4_CR5","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1093\/bioinformatics\/bts716","volume":"29","author":"N. Donmez","year":"2013","unstructured":"Donmez, N., Brudno, M.: SCARPA: scaffolding reads with practical algorithms. Bioinformatics\u00a029(4), 428\u2013434 (2013)","journal-title":"Bioinformatics"},{"issue":"2","key":"4_CR6","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"H.N. Gabow","year":"1976","unstructured":"Gabow, H.N.: An efficient implementation of Edmonds\u2019 algorithm for maximum matching on graphs. Journal of the ACM\u00a023(2), 221\u2013234 (1976)","journal-title":"Journal of the ACM"},{"issue":"11","key":"4_CR7","doi-asserted-by":"publisher","first-page":"1681","DOI":"10.1089\/cmb.2011.0170","volume":"18","author":"S. Gao","year":"2011","unstructured":"Gao, S., Sung, W., Nagarajan, N.: Opera: reconstructing optimal genomic scaffolds with high-throughput paired-end sequences. Journal of Computational Biology\u00a018(11), 1681\u20131691 (2011)","journal-title":"Journal of Computational Biology"},{"key":"4_CR8","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Gritsenko, A.A., Nijkamp, J.F., Reinders, M.J., Ridder, D.D.: GRASS: a generic algorithm for scaffolding next-generation sequencing assemblies. Bioinformatics, 1429\u20131437 (2012)","DOI":"10.1093\/bioinformatics\/bts175"},{"issue":"5","key":"4_CR10","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1145\/585265.585267","volume":"49","author":"D.H. Huson","year":"2002","unstructured":"Huson, D.H., Reinert, K., Myers, E.W.: The greedy path-merging algorithm for contig scaffolding. Journal of ACM\u00a049(5), 603\u2013615 (2002)","journal-title":"Journal of ACM"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Krivelevich, M., Nutov, Z., Salavatipour, M.R., Yuster, J.V., Yuster, R.: Approximation algorithms and hardness results for cycle packing problems. ACM Transaction on Algorithms\u00a03(4) (November 2007)","DOI":"10.1145\/1290672.1290685"},{"issue":"3","key":"4_CR12","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"Sahni, S., Gonzalez, T.: P-complete approximation problems. Journal of ACM\u00a023(3), 555\u2013565 (1976), \n                    \n                      http:\/\/doi.acm.org\/10.1145\/321958.321975","journal-title":"Journal of ACM"},{"key":"4_CR13","unstructured":"Shmoys, D.B., Lenstra, J.K., Kan, A.H.G.R., Lawler, E.L.: The Traveling Salesman Problem: a guided tour of combinatorial optimization. John Wiley & Sons (1985)"},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"2147","DOI":"10.1016\/S0304-3975(02)00577-7","volume":"290","author":"G. Steiner","year":"2003","unstructured":"Steiner, G.: On the k-path partition of graphs. Theoretical Computer Science\u00a0290, 2147\u20132155 (2003)","journal-title":"Theoretical Computer Science"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"W.T. Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Canadian Journal of Mathematics\u00a06, 347\u2013352 (1954)","journal-title":"Canadian Journal of Mathematics"}],"container-title":["Lecture Notes in Computer Science","Algorithms for Computational Biology"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07953-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T01:11:27Z","timestamp":1558919487000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07953-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319079523","9783319079530"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07953-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}