{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T19:34:00Z","timestamp":1791228840755,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642389047","type":"print"},{"value":"9783642389054","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":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38905-4_13","type":"book-chapter","created":{"date-parts":[[2013,5,16]],"date-time":"2013-05-16T03:28:54Z","timestamp":1368674934000},"page":"120-129","source":"Crossref","is-referenced-by-count":8,"title":["Approximating Shortest Superstring Problem Using de Bruijn Graphs"],"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":"13_CR1","unstructured":"Armen, C., Stein, C.: A $2\\frac{3}{4}$-Approximation Algorithm for the Shortest Superstring Problem. Tech. rep., Dartmouth College, Hanover, NH, USA (1994)"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/3-540-60220-8_88","volume-title":"Algorithms and Data Structures","author":"C. Armen","year":"1995","unstructured":"Armen, C., Stein, C.: Improved length bounds for the shortest superstring problem. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol.\u00a0955, pp. 494\u2013505. Springer, Heidelberg (1995)"},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/3-540-61258-0_8","volume-title":"Combinatorial Pattern Matching","author":"C. Armen","year":"1996","unstructured":"Armen, C., Stein, C.: A $2\\frac{2}{3}$-Approximation for the Shortest Superstring Problem. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 87\u2013101. Springer, Heidelberg (1996)"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1145\/103418.103455","volume-title":"Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC 1991","author":"A. Blum","year":"1991","unstructured":"Blum, A., Jiang, T., Li, M., Tromp, J., Yannakakis, M.: Linear approximation of shortest superstrings. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 328\u2013336. ACM, New York (1991)"},{"issue":"2","key":"13_CR5","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1006\/jagm.1997.0861","volume":"24","author":"D. Breslauer","year":"1997","unstructured":"Breslauer, D., Jiang, T., Jiang, Z.: Rotations of periodic strings and short superstrings. J. Algorithms\u00a024(2), 340\u2013353 (1997)","journal-title":"J. Algorithms"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BFb0121091","volume-title":"Netflow at Pisa, Mathematical Programming Studies","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":"13_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":"13_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/3-540-58218-5_9","volume-title":"Algorithm Theory - SWAT 1994","author":"A. Czumaj","year":"1994","unstructured":"Czumaj, A., Gasieniec, L., Piotrow, M., Rytter, W.: Parallel and sequential approximation of shortest superstrings. In: Schmidt, E.M., Skyum, S. (eds.) SWAT 1994. LNCS, vol.\u00a0824, pp. 95\u2013106. Springer, Heidelberg (1994)"},{"issue":"3","key":"13_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":"13_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":"13_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":"13_CR12","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":"1","key":"13_CR13","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.ipl.2004.09.012","volume":"93","author":"H. Kaplan","year":"2005","unstructured":"Kaplan, H., Shafrir, N.: The greedy algorithm for shortest superstrings. Inf. Process. Lett.\u00a093(1), 13\u201317 (2005)","journal-title":"Inf. Process. Lett."},{"key":"13_CR14","unstructured":"Karpinski, M., Schmied, R.: Improved Lower Bounds for the Shortest Superstring and Related Problems. CoRR abs\/1111.5442v3 (2012)"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1109\/SFCS.1994.365696","volume-title":"Proceedings of the 35th Annual Symposium on Foundations of Computer Science, SFCS 1994","author":"S.R. Kosaraju","year":"1994","unstructured":"Kosaraju, S.R., Park, J.K., Stein, C.: Long tours and short superstrings. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, SFCS 1994, pp. 166\u2013177. IEEE Computer Society, Washington, DC (1994)"},{"key":"13_CR16","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 (2013)","DOI":"10.1137\/1.9781611973105.69"},{"key":"13_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-46784-X_7","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Ott","year":"1999","unstructured":"Ott, S.: Lower bounds for approximating shortest superstrings over an alphabet of size 2. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, p. 55. Springer, Heidelberg (1999)"},{"key":"13_CR18","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":"13_CR19","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."},{"key":"13_CR20","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. J. ACM\u00a023, 555\u2013565 (1976)","journal-title":"J. ACM"},{"issue":"3","key":"13_CR21","doi-asserted-by":"publisher","first-page":"954","DOI":"10.1137\/S0097539796324661","volume":"29","author":"Z. Sweedyk","year":"1999","unstructured":"Sweedyk, Z.: $2\\frac{1}{2}$-Approximation Algorithm for Shortest Superstring. SIAM J. Comput.\u00a029(3), 954\u2013986 (1999)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"13_CR22","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","volume":"57","author":"J. Tarhio","year":"1988","unstructured":"Tarhio, J., Ukkonen, E.: A greedy approximation algorithm for constructing shortest common superstrings. Theoretical Computer Science\u00a057(1), 131\u2013145 (1988)","journal-title":"Theoretical Computer Science"},{"key":"13_CR23","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1109\/SFCS.1993.366871","volume-title":"Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, SFCS 1993","author":"S.H. Teng","year":"1993","unstructured":"Teng, S.H., Yao, F.: Approximating shortest superstrings. In: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, SFCS 1993, pp. 158\u2013165. IEEE Computer Society, Washington, DC (1993)"},{"issue":"1","key":"13_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(89)90044-8","volume":"83","author":"J.S. Turner","year":"1989","unstructured":"Turner, J.S.: Approximation algorithms for the shortest common superstring problem. Information and Computation\u00a083(1), 1\u201320 (1989)","journal-title":"Information and Computation"},{"key":"13_CR25","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)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38905-4_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,7]],"date-time":"2023-02-07T14:27:45Z","timestamp":1675780065000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-38905-4_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642389047","9783642389054"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38905-4_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}