{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T19:33:57Z","timestamp":1791228837118,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642403125","type":"print"},{"value":"9783642403132","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40313-2_43","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T10:36:43Z","timestamp":1376649403000},"page":"480-491","source":"Crossref","is-referenced-by-count":3,"title":["Solving 3-Superstring in 3 n\/3 Time"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Golovnev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander S.","family":"Kulikov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ivan","family":"Mihajlin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"43_CR1","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0020-0190(96)00159-7","volume":"60","author":"E. Bax","year":"1996","unstructured":"Bax, E., Franklin, J.: A Finite-Difference Sieve to Count Paths and Cycles by Length. Inf. Process. Lett.\u00a060, 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"43_CR2","doi-asserted-by":"publisher","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\u00a09, 61\u201363 (1962)","journal-title":"J. ACM"},{"key":"43_CR3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1109\/FOCS.2010.24","volume-title":"Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010","author":"A. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, A.: Determinant Sums for Undirected Hamiltonicity. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010, pp. 173\u2013182. IEEE Computer Society, Washington, DC (2010)"},{"issue":"2","key":"43_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2151171.2151181","volume":"8","author":"A. Bj\u00f6rklund","year":"2012","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The traveling salesman problem in bounded degree graphs. ACM Trans. Algorithms 8(2), 18:1\u201318:13 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"43_CR5","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: A Duality between Clause Width and Clause Density for SAT. In: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, CCC 2006, pp. 252\u2013260. IEEE Computer Society (2006)"},{"key":"43_CR6","series-title":"Mathematical Programming Studies","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BFb0121091","volume-title":"Netflow at Pisa","author":"N. Christofides","year":"1986","unstructured":"Christofides, N., Campos, V., Corberan, A., Mota, E.: An algorithm for the Rural Postman problem on a directed graph. In: Netflow at Pisa. Mathematical Programming Studies, vol.\u00a026, pp. 155\u2013166. Springer, Heidelberg (1986)"},{"key":"43_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-13509-5_27","volume-title":"Combinatorial Pattern Matching","author":"M. Crochemore","year":"2010","unstructured":"Crochemore, M., Cygan, M., Iliopoulos, C., Kubica, M., Radoszewski, J., Rytter, W., Wale\u0144, T.: Algorithms for three versions of the shortest common superstring problem. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 299\u2013309. Springer, Heidelberg (2010)"},{"key":"43_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/11814948_26","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"E. Dantsin","year":"2006","unstructured":"Dantsin, E., Wolpert, A.: MAX-SAT for formulas with constant clause density can be solved faster than in O(2\n                  n\n                ) time. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 266\u2013276. Springer, Heidelberg (2006)"},{"issue":"3","key":"43_CR9","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1287\/opre.43.3.399","volume":"43","author":"H.A. Eiselt","year":"1995","unstructured":"Eiselt, H.A., Gendreau, M., Laporte, G.: Arc Routing Problems, Part II: The Rural Postman Problem. Operations Research\u00a043(3), 399\u2013414 (1995)","journal-title":"Operations Research"},{"issue":"1","key":"43_CR10","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a020(1), 50\u201358 (1980)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"43_CR11","doi-asserted-by":"publisher","first-page":"33","DOI":"10.5784\/21-1-17","volume":"21","author":"G. Groves","year":"2005","unstructured":"Groves, G., van Vuuren, J.: Efficient heuristics for the Rural Postman Problem. ORiON\u00a021(1), 33\u201351 (2005)","journal-title":"ORiON"},{"key":"43_CR12","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"Held, M., Karp, R.M.: The Traveling-Salesman Problem and Minimum Spanning Trees. Mathematical Programming\u00a01, 6\u201325 (1971)","journal-title":"Mathematical Programming"},{"key":"43_CR13","doi-asserted-by":"crossref","unstructured":"Hertli, T.: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General. In: Foundations of Computer Science, FOCS, pp. 277\u2013284 (October 2011)","DOI":"10.1109\/FOCS.2011.22"},{"key":"43_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-73545-8_13","volume-title":"Computing and Combinatorics","author":"K. Iwama","year":"2007","unstructured":"Iwama, K., Nakashima, T.: An Improved Exact Algorithm for Cubic Graph TSP. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 108\u2013117. Springer, Heidelberg (2007)"},{"key":"43_CR15","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1145\/1082036.1082041","volume":"52","author":"H. Kaplan","year":"2005","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs. J. ACM\u00a052, 602\u2013626 (2005)","journal-title":"J. ACM"},{"issue":"2","key":"43_CR16","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0167-6377(82)90044-X","volume":"1","author":"R.M. Karp","year":"1982","unstructured":"Karp, R.M.: Dynamic Programming Meets the Principle of Inclusion and Exclusion. Operations Research Letters\u00a01(2), 49\u201351 (1982)","journal-title":"Operations Research Letters"},{"key":"43_CR17","unstructured":"Karpinski, M., Schmied, R.: Improved Lower Bounds for the Shortest Superstring and Related Problems. CoRR abs\/1111.5442 (2011)"},{"key":"43_CR18","doi-asserted-by":"crossref","unstructured":"Kohn, S., Gottlieb, A., Kohn, M.: A Generating Function Approach to the Traveling Salesman Problem. In: ACN 1977: Proceedings of the 1977 Annual Conference, New York, NY, USA, pp. 294\u2013300 (1977)","DOI":"10.1145\/800179.810218"},{"key":"43_CR19","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1515\/DMA.2009.009","volume":"19","author":"A. Kulikov","year":"2009","unstructured":"Kulikov, A., Kutzkov, K.: New upper bounds for the problem of maximal satisfiability. Discrete Mathematics and Applications\u00a019, 155\u2013172 (2009)","journal-title":"Discrete Mathematics and Applications"},{"issue":"2","key":"43_CR20","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1002\/net.3230110211","volume":"11","author":"J.K. Lenstra","year":"1981","unstructured":"Lenstra, J.K., Kan, A.H.G.R.: Complexity of vehicle routing and scheduling problems. Networks\u00a011(2), 221\u2013227 (1981)","journal-title":"Networks"},{"key":"43_CR21","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Nederlof, J.: Saving space by algebraization. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 321\u2013330. ACM (2010)","DOI":"10.1145\/1806689.1806735"},{"key":"43_CR22","doi-asserted-by":"crossref","unstructured":"Moser, R.A., Scheder, D.: A full derandomization of Sch\u00f6ning\u2019s k-SAT algorithm. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 245\u2013252. ACM (2011)","DOI":"10.1145\/1993636.1993670"},{"key":"43_CR23","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, SODA 2013. Society for Industrial and Applied Mathematics (to appear, 2013)","DOI":"10.1137\/1.9781611973105.69"},{"key":"43_CR24","unstructured":"Paluch, K., Elbassioni, K., van Zuylen, A.: Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem. In: STACS 2012. LIPIcs, vol.\u00a014, pp. 501\u2013506 (2012)"},{"issue":"17","key":"43_CR25","doi-asserted-by":"publisher","first-page":"9748","DOI":"10.1073\/pnas.171285098","volume":"98","author":"P.A. Pevzner","year":"2001","unstructured":"Pevzner, P.A., Tang, H., Waterman, M.S.: An Eulerian path approach to DNA fragment assembly. Proc. Natl. Acad. Sci.\u00a098(17), 9748\u20139753 (2001)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"3","key":"43_CR26","doi-asserted-by":"publisher","first-page":"954","DOI":"10.1137\/S0097539796324661","volume":"29","author":"Z. Sweedyk","year":"1999","unstructured":"Sweedyk, Z.: \n                  \n                    \n                  \n                  $2\\frac{1}{2}$\n                -Approximation Algorithm for Shortest Superstring. SIAM J. Comput.\u00a029(3), 954\u2013986 (1999)","journal-title":"SIAM J. Comput."},{"key":"43_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1007\/11549345_68","volume-title":"Mathematical Foundations of Computer Science 2005","author":"V. Vassilevska","year":"2005","unstructured":"Vassilevska, V.: Explicit Inapproximability Bounds for the Shortest Superstring Problem. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 793\u2013800. Springer, Heidelberg (2005)"},{"issue":"2-3","key":"43_CR28","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R. Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science\u00a0348(2-3), 357\u2013365 (2005)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40313-2_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T22:11:19Z","timestamp":1558303879000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40313-2_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403125","9783642403132"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40313-2_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}