{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,21]],"date-time":"2025-04-21T04:26:20Z","timestamp":1745209580137},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_9","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:38:24Z","timestamp":1330270704000},"page":"95-106","source":"Crossref","is-referenced-by-count":11,"title":["Parallel and sequential approximation of shortest superstrings"],"prefix":"10.1007","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[]},{"given":"Leszek","family":"Gasieniec","sequence":"additional","affiliation":[]},{"given":"Marek","family":"Piotr\u00f3w","sequence":"additional","affiliation":[]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"A. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. 33rd FOCS, pp. 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"A. Blum, T. Jiang, M. Li, J. Tromp, and M. Yannakakis. Linear approximation of shortest superstrings. 23rd STOC, pp. 328\u2013336, 1991.","DOI":"10.1145\/103418.103455"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"B. Berger, J. Rompel, and P. W. Shor. Efficient NC algorithms for set cover with applications to learning and geometry. 30th FOCS, pp. 54\u201359, 1989. The full version is to appear in J. Algorithms.","DOI":"10.1109\/SFCS.1989.63455"},{"key":"9_CR4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1979","unstructured":"V. Chvatal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4(1979), pp. 233\u2013235.","journal-title":"Mathematics of Operations Research"},{"key":"9_CR5","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(1980), pp. 50\u201358.","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York, 1979."},{"key":"9_CR7","unstructured":"R. Greenlaw, H. J. Hoover, and W. L. Ruzzo. A compendium of problems complete for P. Technical Report, University of Washington, 1991."},{"key":"9_CR8","unstructured":"M. Li. Towards a DNA sequencing theory (Learning a string). 31st FOCS, 1990."},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. 25th STOC, 1993.","DOI":"10.1145\/167088.167172"},{"key":"9_CR10","unstructured":"C. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982."},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. 20th STOC, pp. 229\u2013234, 1988.","DOI":"10.1145\/62212.62233"},{"key":"9_CR12","unstructured":"H. Peltola, H. Soderlund, J. Tarhio, and E. Ukkonen. Algorithms for some string matching problems arising in molecular genetics. IFIP, pp. 53\u201364, 1983."},{"key":"9_CR13","unstructured":"J. Storer. Data Compression: Methods and theory. Computer Science Press, 1988."},{"key":"9_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), pp. 131\u2013145.","journal-title":"Theoretical Computer Science"},{"key":"9_CR15","unstructured":"S-H. Teng and F. Yao. Approximating shortest superstrings. 34th FOCS, 1993."},{"key":"9_CR16","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. Approximation algorithms for the shortest common superstring problem. Information and Computation 83(1989), pp. 1\u201320.","journal-title":"Information and Computation"},{"key":"9_CR17","unstructured":"V. V. Vazirani. Parallel graph matching. In J. H. Reif, editor, Synthesis of Parallel Algorithms, chapter 18, pp. 783\u2013811. Morgan Kaufmann, 1993."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:18:53Z","timestamp":1605647933000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}