{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:36:59Z","timestamp":1725482219615},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540667315"},{"type":"electronic","value":"9783540467847"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46784-x_7","type":"book-chapter","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T12:02:55Z","timestamp":1175774575000},"page":"55-64","source":"Crossref","is-referenced-by-count":11,"title":["Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2"],"prefix":"10.1007","author":[{"given":"Sascha","family":"Ott","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"7_CR1","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, M. Yannakakis (1994), \u201cLinear approximation of shortest superstrings\u201d, Journal of the ACM, Vol. 41, No. 4, pp. 630\u2013647. 55, 58, 60","journal-title":"Journal of the ACM"},{"key":"7_CR2","unstructured":"P. Crescenzi, V. Kann, R. Silvestri, L. Trevisan (1996), \u201cStructure in Approximation Classes\u201d, Electronic Colloquium on Computational Complexity, TR96-066. 57"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"L. Engebretsen (1999), \u201cAn explicit lower bound for TSP with distances one and two\u201d, Proc.\n                        16th\n                        Annual Symposium on Theoretical Aspects of Computer Science. 56, 62, 63","DOI":"10.1007\/3-540-49116-3_35"},{"key":"7_CR4","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. A. Storer (1980), \u201cOn finding minimal length superstrings\u201d, Journal of Computer and System Sciences, Vol. 20, pp. 50\u201358. 55","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"S. R. Kosaraju, J. K. Park, C. Stein (1994), \u201cLong tours and short superstrings\u201d, Proc. of the\n                        35th\n                        IEEE Symposium on Foundations of Computer Science, pp. 166\u2013177. 56","DOI":"10.1109\/SFCS.1994.365696"},{"key":"7_CR6","unstructured":"M. Li (1990), \u201cTowards a DNA Sequencing Theory\u201d, Proc. of the\n                        31st\n                        IEEE Symposium on Foundations of Computer Science, pp. 125\u2013134. 55"},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)00074-2","volume":"125","author":"M. Middendorf","year":"1994","unstructured":"M. Middendorf (1994), \u201cMore on the complexity of common superstring and supersequence problems\u201d, Theoretical Computer Science, Vol. 125, pp. 205\u2013228. 55","journal-title":"Theoretical Computer Science"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0304-3975(97)00133-3","volume":"191","author":"M. Middendorf","year":"1998","unstructured":"M. Middendorf (1998), \u201cShortest common superstrings and scheduling with coordinated starting times\u201d, Theoretical Computer Science, Vol. 191, pp. 205\u2013214. 55","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"7_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. Papadimitriou","year":"1993","unstructured":"C. Papadimitriou, M. Yannakakis (1993), \u201cThe traveling salesman problem with distances one and two\u201d, Mathematics of Operations Research, Vol. 18(1), pp. 1\u201311. 57, 58","journal-title":"Mathematics of Operations Research"},{"key":"7_CR10","unstructured":"J. Storer (1988), \u201cData compression: methods and theory\u201d, Computer Science Press. 56"},{"key":"7_CR11","unstructured":"Z Sweedyk (1999), \u201cA 2-12 approximation algorithm for shortest superstring\u201d, SIAM Journal on Computing, to appear. 56"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(89)90044-8","volume":"83","author":"J. S. Turner","year":"1989","unstructured":"J. S. Turner (1989), \u201cApproximation algorithms for the shortest common superstring problem\u201d, Information and Computation, Vol. 83, pp. 1\u201320. 57","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46784-X_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T07:40:12Z","timestamp":1550302812000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46784-X_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540667315","9783540467847"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-46784-x_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}