{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T10:53:40Z","timestamp":1648810420616},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,7,28]],"date-time":"2016-07-28T00:00:00Z","timestamp":1469664000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Government of the Russian Federation","award":["14.Z50.31.0030","14.Z50.31.0030"],"award-info":[{"award-number":["14.Z50.31.0030","14.Z50.31.0030"]}]},{"name":"Government of the Russian Federation","award":["14.Z50.31.0030","14.Z50.31.0030"],"award-info":[{"award-number":["14.Z50.31.0030","14.Z50.31.0030"]}]},{"name":"Government of the Russian Federation","award":["14.Z50.31.0030"],"award-info":[{"award-number":["14.Z50.31.0030"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00453-016-0193-0","type":"journal-article","created":{"date-parts":[[2016,7,28]],"date-time":"2016-07-28T14:21:08Z","timestamp":1469715668000},"page":"798-813","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity of Superstring Problems"],"prefix":"10.1007","volume":"79","author":[{"given":"Ivan","family":"Bliznets","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolay","family":"Karpov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander S.","family":"Kulikov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,28]]},"reference":[{"key":"193_CR1","unstructured":"Concorde TSP Solver. http:\/\/www.math.uwaterloo.ca\/tsp\/concorde.html"},{"issue":"1","key":"193_CR2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM (JACM) 9(1), 61\u201363 (1962)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"193_CR3","doi-asserted-by":"crossref","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. Discret. Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discret. Math."},{"key":"193_CR4","unstructured":"Bulteau, L., H\u00fcffner, F., Komusiewicz, C., Niedermeier, R.: Multivariate algorithmics for NP-hard string problems. Bull. EATCS 114 (2014)"},{"key":"193_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"193_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Texts in Computer Science (2013)"},{"key":"193_CR7","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with $$0,1$$ 0 , 1 -vertices. J. Res. Nat. Bur. Stand. Sect. B 69B, 125\u2013130 (1965)","journal-title":"J. Res. Nat. Bur. Stand. Sect. B"},{"key":"193_CR8","doi-asserted-by":"crossref","unstructured":"Evans, P.A., Wareham, T.: Efficient restricted-case algorithms for problems in computational biology. Algorithms in Computational Molecular Biology: Techniques. Approaches and Applications, pp. 27\u201349. Wiley, Wiley Series in Bioinformatics (2011)","DOI":"10.1002\/9780470892107.ch2"},{"key":"193_CR9","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Representative sets of product families. In: Algorithms-ESA 2014, pp. 443\u2013454. Springer (2014)","DOI":"10.1007\/978-3-662-44777-2_37"},{"issue":"1","key":"193_CR10","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J Gallant","year":"1980","unstructured":"Gallant, J., Maier, D., Storer, J.A.: On finding minimal length superstrings. J. Comput. Syst. Sci. 20(1), 50\u201358 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"193_CR11","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, New York (1979)"},{"key":"193_CR12","doi-asserted-by":"crossref","unstructured":"Golovnev, A., Kulikov, A.S., Mihajlin, I.: Solving 3-superstring in $$3^{n\/3}$$ 3 n \/ 3 time. In: Mathematical Foundations of Computer Science 2013, pp. 480\u2013491. Springer (2013)","DOI":"10.1007\/978-3-642-40313-2_43"},{"issue":"8","key":"193_CR13","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1016\/j.ipl.2014.03.004","volume":"114","author":"A Golovnev","year":"2014","unstructured":"Golovnev, A., Kulikov, A.S., Mihajlin, I.: Solving SCS for bounded length strings in fewer than $$2^n$$ 2 n steps. Inf. Process. Lett. 114(8), 421\u2013425 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"193_CR14","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196\u2013210 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"2","key":"193_CR15","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0167-6377(82)90044-X","volume":"1","author":"RM Karp","year":"1982","unstructured":"Karp, R.M.: Dynamic programming meets the principle of inclusion and exclusion. Op. Res. Lett. 1(2), 49\u201351 (1982)","journal-title":"Op. Res. Lett."},{"key":"193_CR16","doi-asserted-by":"crossref","unstructured":"Kohn, S., Gottlieb, A., Kohn, M.: A generating function approach to the traveling salesman problem. In: Proceedings of the 1977 annual conference. pp. 294\u2013300. ACM (1977)","DOI":"10.1145\/800179.810218"},{"key":"193_CR17","doi-asserted-by":"crossref","unstructured":"Mucha, M.: Lyndon words and short superstrings. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 958\u2013972. SIAM (2013)","DOI":"10.1137\/1.9781611973105.69"},{"issue":"6","key":"193_CR18","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length k in $$O^{*}(2^k)$$ O \u2217 ( 2 k ) time. Inf. Process. Lett. 109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0193-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0193-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0193-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0193-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T21:26:09Z","timestamp":1568237169000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0193-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,28]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["193"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0193-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,28]]}}}