{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:40:08Z","timestamp":1742596808673,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571551"},{"type":"electronic","value":"9783540479185"}],"license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"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":[[1993]]},"DOI":"10.1007\/3-540-57155-8_264","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:06:10Z","timestamp":1330257970000},"page":"385-396","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximating shortest superstrings with constraints"],"prefix":"10.1007","author":[{"given":"Tao","family":"Jiang","sequence":"first","affiliation":[]},{"given":"Ming","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"A. Blum, T. Jiang, M. Li, J. Tromp, M. Yannakakis. Linear approximation of shortest superstrings. Proc, 23rd ACM Symp. on Theory of Computing, 1991, 328\u2013336; also to appear in J. ACM.","DOI":"10.1145\/103418.103455"},{"key":"36_CR2","first-page":"59","volume":"1\u20131","author":"R. Drmanac","year":"1992","unstructured":"R. Drmanac and C. Crkvenjakov. Sequencing by hybridization (SBH) with oligonucleotide probes as an integral appraoch for the analysis of complex genomes. International Journal of Genomic Research 1\u20131, 1992, 59\u201379.","journal-title":"International Journal of Genomic Research"},{"key":"36_CR3","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, J. Storer. On finding minimal length superstring. Journal of Computer and System Sciences 20, 1980, 50\u201358.","journal-title":"Journal of Computer and System Sciences"},{"key":"36_CR4","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson. Computers and Intractability. Freeman, New York, 1979."},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"A. Hoffman. On simple linear programming problems. Convexity: Proc. of Symposia in Pure Mathematics, Vol. 7 (V. Klee, Ed.). American Mathematical Society, 1963.","DOI":"10.1090\/pspum\/007\/0157778"},{"key":"36_CR6","unstructured":"T. Jiang and M. Li. Towards a DNA sequencing theory (revised version). Submitted to Information and Computation, 1991."},{"key":"36_CR7","doi-asserted-by":"crossref","unstructured":"T. Jiang and M. Li. On the complexity of learning strings and sequences. Proc. 4th Workshop on Computational Learning, 1991, 367\u2013371; also to appear in Theoretical Computer Science 119, 1993.","DOI":"10.1016\/0304-3975(93)90167-R"},{"key":"36_CR8","unstructured":"A. Lesk (Edited). Computational Molecular Biology, Sources and Methods for Sequence Analysis. Oxford University Press, 1988."},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"M. Li. Towards a DNA sequencing theory. Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990, 125\u2013134.","DOI":"10.1109\/FSCS.1990.89531"},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"P. Pevzner and R. Lipshutz. Towards DNA sequencing by hybridization. Manuscript, 1993.","DOI":"10.1007\/3-540-58338-6_64"},{"key":"36_CR11","unstructured":"C. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982."},{"key":"36_CR12","unstructured":"H. Peltola, H. Soderlund, J. Tarhio, and E. Ukkonen. Algorithms for some string matching problems arising in molecular genetics. Information Processing 83 (Proc. IFIP Congress), 1983, 53\u201364."},{"key":"36_CR13","unstructured":"J. Storer. Data compression: methods and theory. Computer Science Press, 1988."},{"key":"36_CR14","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, 1988, 131\u2013145.","journal-title":"Theoretical Computer Science"},{"key":"36_CR15","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, 1989, 1\u201320.","journal-title":"Information and Computation"},{"issue":"11","key":"36_CR16","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"L. G. Valiant. A theory of the learnable. Comm. ACM 27(11), 1984, 1134\u20131142.","journal-title":"Comm. ACM"}],"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-57155-8_264","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:00:17Z","timestamp":1742594417000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_264"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_264","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"9 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}