{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,21]],"date-time":"2025-04-21T04:26:16Z","timestamp":1745209576067,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540612582"},{"type":"electronic","value":"9783540683902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61258-0_8","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:21:19Z","timestamp":1330291279000},"page":"87-101","source":"Crossref","is-referenced-by-count":16,"title":["A 2 2\/3-approximation algorithm 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":"8_CR1","doi-asserted-by":"crossref","unstructured":"C. Armen and C.Stein. Improved length bounds for the shortest superstring problem. In Proceedings of Workshop on Algorithms and Data Structures, pages 494\u2013505, 1995.","DOI":"10.1007\/3-540-60220-8_88"},{"key":"8_CR2","unstructured":"C. Armen and C. Stein. A 2 2\/3-approximation algorithm for the shortest superstring problem. Technical Report PCS-TR95-262, Dartmouth College, June 1995."},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"C. Armen and C. Stein. Short superstrings and the structure of overlapping strings. To appear in J. of Computational Biology, 1996.","DOI":"10.1089\/cmb.1995.2.307"},{"key":"8_CR4","unstructured":"Chris Armen. Approximation Algorithms for the Shortest Superstring Problem. PhD thesis, Dartmouth College, July 1995."},{"issue":"4","key":"8_CR5","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":"8_CR6","unstructured":"Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. MIT Press\/McGraw-Hill, 1990."},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"A. Czumaj, L. Gasieniec, M. Piotrow, and W. Rytter. Parallel and sequential approximations 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":"8_CR8","unstructured":"A. Lesk (edited). Computational Molecular Biology, Sources and Methods for Sequence Analysis. Oxford University Press, 1988."},{"key":"8_CR9","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":"8_CR10","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":"8_CR11","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":"8_CR12","unstructured":"Tao Jiang and Zhigen Jiang. Rotation of periodic strings and short superstrings. Unpublished Manuscript courtesy Tao Jiang March 1996."},{"key":"8_CR13","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/0304-3975(94)90249-6","volume":"134","author":"T. Jiang","year":"1994","unstructured":"Tao Jiang and Ming Li. Approximating shortest superstrings with constraints. Therotical Computer Science, (134):473\u2013491, 1994.","journal-title":"Therotical Computer Science"},{"issue":"1\/2","key":"8_CR14","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF01188580","volume":"13","author":"J.D. Kececioglu","year":"1995","unstructured":"J.D. Kececioglu and E.W. Myers. Combinatorial algorithms for dna sequence assembly. Algorithmica, 13(1\/2):7\u201351, 1995.","journal-title":"Algorithmica"},{"key":"8_CR15","unstructured":"John D. Kececioglu. Exact and approximation algorithms for DNA sequence reconstruction. PhD thesis, University of Arizona, 1991."},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"R. Kosaraju, J. Park, and C. Stein. Long tours and short superstrings. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, November 1994.","DOI":"10.1109\/SFCS.1994.365696"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"M. Li. Towards a DNA sequencing theory (learning a string). In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 125\u2013134, 1990.","DOI":"10.1109\/FSCS.1990.89531"},{"key":"8_CR18","volume-title":"Combinatorial Optimization, Algorithms and Complexity","author":"H. Christos","year":"1982","unstructured":"Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial Optimization, Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982."},{"key":"8_CR19","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":"8_CR20","doi-asserted-by":"crossref","unstructured":"Graham A. Stephen. String searching algorithms. World Scientific, 1994.","DOI":"10.1142\/9789814317368"},{"key":"8_CR21","unstructured":"J. Storer. Data compression: methods and theory. Computer Science Press, 1988."},{"key":"8_CR22","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":"8_CR23","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","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61258-0_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:15:31Z","timestamp":1742598931000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61258-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540612582","9783540683902"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-61258-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}