{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:29Z","timestamp":1740109289971,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2018,1,29]],"date-time":"2018-01-29T00:00:00Z","timestamp":1517184000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s00453-018-0405-x","type":"journal-article","created":{"date-parts":[[2018,1,29]],"date-time":"2018-01-29T09:24:57Z","timestamp":1517217897000},"page":"1771-1803","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Scaffolding Problems Revisited: Complexity, Approximation and Fixed Parameter Tractable Algorithms, and Some Special Cases"],"prefix":"10.1007","volume":"80","author":[{"given":"Mathias","family":"Weller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4760-8171","authenticated-orcid":false,"given":"Annie","family":"Chateau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cl\u00e9ment","family":"Dallard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodolphe","family":"Giroudeau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,1,29]]},"reference":[{"key":"405_CR1","unstructured":"Alimonti, P., Ausiello, G., Giovaniello, L., Protasi, M.: On the complexity of approximating weighted satisfiability problems. Tech. rep., Universit\u00e0 degli Studi di Roma La Sapienza, rapporto Tecnico RAP 38.97 (1997)"},{"issue":"1","key":"405_CR2","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/s10878-011-9449-4","volume":"26","author":"C Bazgan","year":"2012","unstructured":"Bazgan, C., Toubaline, S., Vanderpooten, D.: Critical edges\/nodes for the minimum spanning tree problem: complexity and approximation. J. Comb. Optim. 26(1), 178\u2013189 (2012)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"405_CR3","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00373-013-1380-2","volume":"31","author":"C Bazgan","year":"2015","unstructured":"Bazgan, C., Bentz, C., Picouleau, C., Ries, B.: Blockers for the stability number and the chromatic number. Graphs Comb. 31(1), 73\u201390 (2015)","journal-title":"Graphs Comb."},{"key":"405_CR4","first-page":"47","volume-title":"Algorithms and Complexity\u20149th International Conference, CIAC 2015, Paris, France, May 20\u201322, 2015. Proceedings, Lecture Notes in Computer Science","author":"C Bazgan","year":"2015","unstructured":"Bazgan, C., Nichterlein, A., Niedermeier, R.: A refined complexity analysis of finding the most vital edges for undirected shortest paths. In: Paschos, V.T., Widmayer, P. (eds.) Algorithms and Complexity\u20149th International Conference, CIAC 2015, Paris, France, May 20\u201322, 2015. Proceedings, Lecture Notes in Computer Science, vol. 9079, pp. 47\u201360. Springer, Berlin (2015)"},{"issue":"1\u20132","key":"405_CR5","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybern."},{"key":"405_CR6","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Treewidth of graphs. In: Ming-Yang, K. (ed.) Encyclopedia of Algorithms, pp. 2255\u20132257. Springer, New York (2016)","DOI":"10.1007\/978-1-4939-2864-4_431"},{"issue":"1","key":"405_CR7","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20133","key":"405_CR8","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0012-365X(94)00296-U","volume":"152","author":"A Brandst\u00e4dt","year":"1996","unstructured":"Brandst\u00e4dt, A.: Partitions of graphs into one or two independent sets and cliques. Discrete Math. 152(1\u20133), 47\u201354 (1996)","journal-title":"Discrete Math."},{"key":"405_CR9","doi-asserted-by":"crossref","unstructured":"Chateau, A., Giroudeau, R.: Complexity and polynomial-time approximation algorithms around the scaffolding problem. In: Proceedings of AlCoB \u201914, LNCS, vol. 8542, pp. 47\u201358. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-07953-0_4"},{"key":"405_CR10","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2015.06.023","volume":"595","author":"A Chateau","year":"2015","unstructured":"Chateau, A., Giroudeau, R.: A complexity and approximation framework for the maximization scaffolding problem. Theoret. Comput. Sci. 595, 92\u2013106 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"405_CR11","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D.W., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201(2), 216\u2013231 (2005)","journal-title":"Inf. Comput."},{"key":"405_CR12","doi-asserted-by":"crossref","unstructured":"Crescenzi, P.: A short guide to approximation preserving reductions. In: Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, June 24\u201327, 1997, pp. 262\u2013273 (1997)","DOI":"10.1109\/CCC.1997.612321"},{"key":"405_CR13","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., Sengupta, A.: SOPRA: Scaffolding algorithm for paired reads via statistical optimization. BMC Bioinform. 11, 345 (2010)","journal-title":"BMC Bioinform."},{"key":"405_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"issue":"11","key":"405_CR15","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.K., Nagarajan, N.: Opera: reconstructing optimal genomic scaffolds with high-throughput paired-end sequences. J. Comput. Biol. 18(11), 1681\u20131691 (2011)","journal-title":"J. Comput. Biol."},{"key":"405_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"405_CR17","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\varepsilon }$$ n 1 - \u03b5 . Electronic Colloquium on Computational Complexity (ECCC) 4(38) (1997)"},{"issue":"3","key":"405_CR18","doi-asserted-by":"publisher","first-page":"R42","DOI":"10.1186\/gb-2014-15-3-r42","volume":"15","author":"M Hunt","year":"2014","unstructured":"Hunt, M., Newbold, C., Berriman, M., Otto, T.: A comprehensive evaluation of assembly scaffolding tools. Genome Biol. 15(3), R42 (2014)","journal-title":"Genome Biol."},{"issue":"2","key":"405_CR19","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$ k -SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"405_CR20","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"405_CR21","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"issue":"4","key":"405_CR22","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","volume":"8","author":"J Plesn\u00edk","year":"1979","unstructured":"Plesn\u00edk, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett. 8(4), 199\u2013201 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"Suppl 14","key":"405_CR23","doi-asserted-by":"publisher","first-page":"S2","DOI":"10.1186\/1471-2105-16-S14-S2","volume":"16","author":"M Weller","year":"2015","unstructured":"Weller, M., Chateau, A., Giroudeau, R.: Exact approaches for scaffolding. BMC Bioinform. 16(Suppl 14), S2 (2015)","journal-title":"BMC Bioinform."},{"key":"405_CR24","first-page":"409","volume-title":"Combinatorial Optimization and Applications\u20149th International Conference, COCOA 2015, Houston, TX, USA, December 18\u201320, 2015, Proceedings, Lecture Notes in Computer Science","author":"M Weller","year":"2015","unstructured":"Weller, M., Chateau, A., Giroudeau, R.: On the complexity of scaffolding problems: from cliques to sparse graphs. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D. (eds.) Combinatorial Optimization and Applications\u20149th International Conference, COCOA 2015, Houston, TX, USA, December 18\u201320, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9486, pp. 409\u2013423. Springer, Berlin (2015)"},{"key":"405_CR25","doi-asserted-by":"crossref","unstructured":"Woeginger, G.: Exact algorithms for np-hard problems: a survey. In: Combinatorial Optimization\u2014Eureka, You Shrink!, Lecture Notes in Computer Science, vol. 2570, pp. 185\u2013207. Springer, Berlin (2003)","DOI":"10.1007\/3-540-36478-1_17"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0405-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0405-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0405-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,9]],"date-time":"2019-10-09T18:38:22Z","timestamp":1570646302000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0405-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,29]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["405"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0405-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,1,29]]},"assertion":[{"value":"20 April 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}