{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,21]],"date-time":"2025-04-21T04:26:17Z","timestamp":1745209577221,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602200"},{"type":"electronic","value":"9783540447474"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"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":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_88","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:53:22Z","timestamp":1330278802000},"page":"494-505","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Improved length bounds for the shortest superstring problem"],"prefix":"10.1007","author":[{"given":"Chris","family":"Armen","sequence":"first","affiliation":[]},{"given":"Clifford","family":"Stein","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"43_CR1","doi-asserted-by":"crossref","unstructured":"C. Armen and C. Stein. Short supertrings and the structure of overlapping strings. To appear in J. of Computational Biology, 1995.","DOI":"10.1089\/cmb.1995.2.307"},{"issue":"4","key":"43_CR2","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1145\/179812.179818","volume":"41","author":"A. Blum","year":"1994","unstructured":"A. Blum, T. Jiang, M. Li, J. Tromp, and M. Yannakakis. Linear approximation of shortest superstrings. Journal of the ACM, 41(4):630\u2013647, July 1994.","journal-title":"Journal of the ACM"},{"key":"43_CR3","doi-asserted-by":"crossref","unstructured":"A. Czumaj, L. Gasieniec, M. Piotrow, and W. Rytter. Parallel and sequential approxmations of shortest superstrings. In Proceedings of Fourth Scandinavian Workshop on Algorithm Theory, pages 95\u2013106, 1994.","DOI":"10.1007\/3-540-58218-5_9"},{"key":"43_CR4","unstructured":"A. Lesk (edited). Computational Molecular Biology, Sources and Methods for Sequence Analysis. Oxford University Press, 1988."},{"key":"43_CR5","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"A.M. Frieze","year":"1982","unstructured":"A.M. Frieze, G. Galbiati, and F. Maffoli. On the worst case performance of some algorithms for the asymmetric travelling salesman problem. Networks, 12:23\u201339, 1982.","journal-title":"Networks"},{"key":"43_CR6","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J. Gallant","year":"1980","unstructured":"J. Gallant, D. Maier, and J. Storer. On finding minimal length superstrings. Journal of Computer and System Sciences, 20:50\u201358, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"43_CR7","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0020-0190(94)00097-2","volume":"51","author":"D. Gusfield","year":"1994","unstructured":"D. Gusfield. Faster implementation of a shortest superstring approximation. Information Processing Letters, (51):271\u2013274, 1994.","journal-title":"Information Processing Letters"},{"key":"43_CR8","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0020-0190(92)90176-V","volume":"41","author":"D. Gusfield","year":"1992","unstructured":"D. Gusfield, G. Landau, and B. Schieber. An efficient algorithm for the all pairs suffix-prefix problem. Information Processing Letters, (41):181\u2013185, March 1992.","journal-title":"Information Processing Letters"},{"key":"43_CR9","unstructured":"John D. Kececioglu. Exact and approximation algorithms for DNA sequence reconstruction. PhD thesis, University of Arizona, 1991."},{"key":"43_CR10","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"D.E. Knuth, J.H.Morris, and V.B. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6:189\u2013195, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"43_CR11","unstructured":"R. Kosaraju, J. Park, and C. Stein. Long tours and short superstrings. In FOCS, November 1994."},{"key":"43_CR12","doi-asserted-by":"crossref","unstructured":"M. Li. Towards a DNA sequencing theory (learning a string). In FOCS, pages 125\u2013134, 1990.","DOI":"10.1109\/FSCS.1990.89531"},{"key":"43_CR13","first-page":"247","volume":"17","author":"L.J. Cummings","year":"1983","unstructured":"L.J.Cummings. Strongly qth power-free strings. Annals of Discrete Mathematics, 17:247\u2013252, 1983.","journal-title":"Annals of Discrete Mathematics"},{"key":"43_CR14","volume-title":"Combinatorial Optimization, Algorithms and Complexity","author":"C. H. Papadimitriou","year":"1982","unstructured":"Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial Optimization, Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982."},{"key":"43_CR15","unstructured":"H. Peltola, H. Soderlund, J. Tarjio, and E. Ukkonen. Algorithms for some string matching problems arising in molecular genetics. In Proceedings of the IFIP Congress, pages 53\u201364, 1983."},{"key":"43_CR16","doi-asserted-by":"crossref","unstructured":"Graham A. Stephen. String searching algorithms. World Scientific, 1994.","DOI":"10.1142\/2418"},{"key":"43_CR17","unstructured":"J. Storer. Data compression: methods and theory. Computer Science Press, 1988."},{"key":"43_CR18","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","volume":"57","author":"J. Tarhio","year":"1988","unstructured":"J. Tarhio and E. Ukkonen. A greedy approximation algorithm for constructing shortest common superstrings. Theoretical Computer Science, 57:131\u2013145, 1988.","journal-title":"Theoretical Computer Science"},{"key":"43_CR19","doi-asserted-by":"crossref","unstructured":"Shang-Hua Teng and Frances Yao. Approximating shortest superstrings. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pages 158\u2013165, November 1993.","DOI":"10.1109\/SFCS.1993.366871"},{"key":"43_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(89)90044-8","volume":"83","author":"J. Turner","year":"1989","unstructured":"J. Turner. Approximation algorithms for the shortest common superstring problem. Information and Computation, 83:1\u201320, 1989.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_88","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:56:00Z","timestamp":1742597760000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_88"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_88","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}